java - 从总和等于给定数字的数组中计算对？

Question

我刚刚进行了一次在线编码面试，其中一个问题是对于给定的整数数组，找出总和等于某个数字的对的数量(作为方法内部的参数传递)。例如，给出一个数组，

int[] a = {3, 2, 1, 45, 27, 6, 78, 9, 0};
int k = 9; // given number

因此，将有 2 对 (3, 6) 和 (9, 0)，其总和等于 9。值得一提的是，这些对的形成方式并不重要。均值 (3,6) 和 (6,3) 将被视为同一对。我提供了以下解决方案(在 Java 中)并且很想知道我是否遗漏了任何边缘情况？

public static int numberOfPairs(int[] a, int k ){

    int len = a.length;

    if (len == 0){
      return -1;
    }

    Arrays.sort(a);
    int count  = 0, left = 0, right = len -1; 

    while( left < right ){

        if ( a[left] + a[right] == k  ){

            count++; 

            if (a[left] == a[left+1] && left < len-1 ){
              left++;
            }

            if ( a[right] == a[right-1] && right >1 ){
              right-- ; 
            }

            right--; // right-- or left++, otherwise, will get struck in the while loop 
        }

        else if ( a[left] + a[right] < k ){
          left++;
        }

        else {
          right--;
        }
    }

    return count; 
}

此外，任何人都可以提出该问题的任何替代解决方案吗？谢谢。

Answer 1

以下解决方案将返回唯一对

的数量

public static int numberOfPairs(Integer[] array, int sum) {
    Set<Integer> set = new HashSet<>(Arrays.asList(array));

    // this set will keep track of the unique pairs.
    Set<String> uniquePairs = new HashSet<String>();

    for (int i : array) {
        int x = sum - i;
        if (set.contains(x)) {
            int[] y = new int[] { x, i };
            Arrays.sort(y);
            uniquePairs.add(Arrays.toString(y));
        }
    }

    //System.out.println(uniquePairs.size());
    return uniquePairs.size();
}

时间复杂度为O(n)。

希望这对您有所帮助。