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

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

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 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 set = new HashSet<>(Arrays.asList(array)); // this set will keep track of the unique pairs. Set uniquePairs = new HashSet(); 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） 。

希望这可以帮助。

Answer 2

您的解决方案过于复杂，您可以更轻松地完成此练习：

 public static int numberOfPairs(int[] a, int k ){ int count=0; List dedup = new ArrayList<>(new HashSet<>(Arrays.asList(a))); for (int x=0 ; x < dedup.size() ; x++ ){ for (int y=x+1 ; y < dedup.size() ; y++ ){ if (dedup.get(x)+dedup.get(y) == k) count++; } } return count; } 

这里的技巧是在第一个循环的索引之后开始循环，不要将相同的值计数两次，而不是将它与您自己的索引进行比较。 此外，您可以对数组进行重复数据删除以避免重复对，因为它们无关紧要。

您也可以对列表进行排序，然后在总和超过k立即break循环，但这是优化。

Answer 3

给定整数数组和目标值，确定差异等于目标值的数组元素对的数量。 该函数具有以下参数：

k ：整数，目标差异

arr ：一个整数数组

使用LINQ这是一个很好的解决方案：

  public static int CountNumberOfPairsWithDiff(int k, int[] arr) { var numbers = arr.Select((value) => new { value }); var pairs = from num1 in numbers join num2 in numbers on num1.value - k equals num2.value select new[] { num1.value, // first number in the pair num2.value, // second number in the pair }; foreach (var pair in pairs) { Console.WriteLine("Pair found: " + pair[0] + ", " + pair[1]); } return pairs.Count(); }