Java

Question

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

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

例子

成对([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 开始第二个循环，而不是 0。

for(int i = 0; i < 10; i++)
{
 for(int j = i; j < 10; j ++)
   {
       System.out.println("(" + i + "," + j + ")");
   }  
}

Output:
I reduced `10` to `4`.
    (0,0)
    (0,1)
    (0,2)
    (0,3)
    (0,4)
    (1,1)
    (1,2)
    (1,3)
    (1,4)
    (2,2)
    (2,3)
    (2,4)
    (3,3)
    (3,4)
    (4,4)

Answer 2

最简单的选择是首先不检查这些。我认为 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;
}

打印

这可确保您不会两次重复相同的数字。

注意：这是一种 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
    }
}

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

Java - how to stop nested loops from checking same indices twice?

arrays

nested-loops