计算总和等于给定数字的数组对？

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).

希望这可以帮助.