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
    }
}