计算总和等于给定数字的数组对？ [英] Count pairs from an array whose sum is equal to a given number?

问题描述

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

I just had an online coding interview and one of the questions asked there is for a given array of integers, find out the number of pairs whose summation is equal to a certain number (passed as parameter inside the method ). For example an array is given as,

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）并且很想知道我是否错过了任何边缘情况？

So, there will be 2 pairs (3, 6) and (9, 0) whose sum is equal to 9. It's good to mention that how the pairs are formed doesn't matter. The means (3,6) and (6,3) will be considered as same pair. I provided the following solution (in Java) and curious to know if I missed any edge cases?

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

此外，有人可以提出任何替代解决方案吗？谢谢。

Besides, can anyone propose any alternative solution of the problem ? Thanks.

推荐答案

请检查以下代码。

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） 。

希望这会有所帮助。

这篇关于计算总和等于给定数字的数组对？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！