Java - 如何阻止嵌套循环检查相同的索引两次？

Question

给定一个数组和一个数字 N，如果它们的和等于 N，则称数组中的一对数字为完美对。

找到所有的完美对并返回它们索引的总和。请注意，数组的任何元素只能算在一个完美对中。

例子

成对([1, 4, 2, 3, 0, 5], 7) = 11 由于完美对是 (4, 3) 和 (2, 5)，索引为 1 + 3 + 2 + 5 = 11。

成对([1, 3, 2, 4], 4) = 1 由于索引 0 处的元素(即 1)和索引 1 处的元素(即 3)形成唯一的完美对。

输入 1 (arr) → array.integer : 非负整数数组

输入 2 (N) → 整数: 正整数

输出 → 整数: 索引之和，如果不存在完美对则为 0

我的代码:

     public static void main(String[] args) {
        int x[] = {1,4,2,3,0,5};
        System.out.println(pairwise(x, 7)); 
    }

     public static int pairwise(int[] arr, int N) {    
        int t=0;
        for(int i=0;i<arr.length;i++){
          for(int k=0;k<arr.length;k++){
            if(arr[i]+arr[k] == N){
              t+=i+k;
            } 
          }
        }
        return t;
     }

问题是我的代码检查索引两次，例如 (0,1) 和 (1,0) 被视为不同的索引。

Answer 1

最简单的选择是首先不检查这些。我假设 i == k无效，因此您不想检查 k < i要么。

public static void main(String[] args) {
    int x[] = {1, 4, 2, 3, 0, 5};
    System.out.println(pairwise(x, 7));
}

public static int pairwise(int[] arr, int N) {
    int t = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int k = i + 1; k < arr.length; k++) {
            if (arr[i] + arr[k] == N) {
                t += i + k;
                arr[i] = arr[k] = Integer.MIN_VALUE; // don't use these again
                continue;
            }
        }
    }
    return t;
}

打印

11

这可确保您不会两次检查相同的数字。

注意:这是一种 O(n^2) 方法，如果您有更多数字，您将需要 O(n) 方法，这意味着使用数字集或数字映射。

// O(n)
Map<Integer, Integer> intToIndex = new HashMap<>();
for(int i = 0; i < arr.length; i++)
    intToIndex.put(arr[i], i);

// O(n)
for(int i = 0; i < arr.length; i++) {
    int numberToLookFor = N - arr[i];
    Integer k = intToIndex.get(numberToLookFor);
    if (k != null) {
        assert arr[i] + arr[k] == N;
        // do something with i and k
    }
}