如何在数组中找到两个总和为k的元素

假设您获得了一组未排序的整数

A = {3,4,5,1,4,2} 

输入： 6输出： {5,1}, {4,2}

如何在O（n）或O（log n）中执行此操作。 任何建议将不胜感激。

更新：我们能写一些比这更有效的东西吗？

 for(int i=0;i<array.length-1;i++) { if(array[i]+array[i+1]==6) System.out.println("{"+array[i]+","+array[i+1]+"}"); } 

Answer 1

如果存储在输入数组中的数字只是正数，那么我将创建另一个k + 1个ArrayList元素的数组K. 其中k是你需要它们加起来的数字。 只有两个小于k的数字可以加起来k（假设我们处理正整数}或者在特殊情况下{0，k}。然后我将迭代输入数组的所有元素，并且对于每个小于或等于k我将其索引并将索引添加到索引为m的ArrayList K数组中。然后我将迭代数组K的前半部分，对于每个存储有一些整数的索引，我会找到互补索引[ ki]并查看其中是否有任何值。如果有，那么这些是你的对。顺便说一下这是O（n）。

 public static void findElemtsThatSumTo( int data[], int k){ List arrayK[]= new List[k+1]; for(int i=0; i(); for(int i=0; i 

Answer 2

与您的其他问题一样，O（log n ）是不可能的，因为您必须检查整个数组。 但O（n）或多或少是可能的。

如果你的可能整数范围相对较小 – 也就是说，如果它在n的常数因子内 – 那么你可以写：

 final boolean[] seen = new boolean[max - min + 1]; for(final int a : A) { if(seen[input - a - min]) System.out.println("{" + (input - a) + "," + a + "}"); seen[a - min] = true; } 

如果没有，你可以做同样的事情，但使用HashSet而不是数组：

 final Set seen = new HashSet(); for(final int a : A) { if(seen.contains(input - a)) System.out.println("{" + (input - a) + "," + a + "}"); seen.add(a); } 

但这不会保证 O（n）时间。

Answer 3

 public static void main(String[] args) { // TODO Auto-generated method stub int arr[]={4,2,6,8,9,3,1}; int sum=10; int arr1[]=new int[sum]; for(int x=0;x 

Answer 4

关于O（n）复杂性与O（n）额外内存的这个问题我的小答案。 此代码段返回所有唯一索引元素对，其中和K.

 /** * Returns indices of all complementary pairs in given {@code arr} with factor {@code k}. Two elements {@code arr[i]} and {@code arr[j]} are * complementary if {@code arr[i] + arr[j] = k}. * Method returns set of pairs in format {@literal [i,j]}. Two pairs {@literal [i,j]} and {@literal [j,i]} are treated as same, and only one pair * is returned. * Method support negative numbers in the {@code arr}, as wel as negative {@code k}. * 
 * Complexity of this method is O(n), requires O(n) additional memory. * * @param arr source array * @param k factor number * @return not {@code null} set of all complementary pairs in format {@literal [i,j]} */ public static Set getComplementaryPairs(int[] arr, int k) { if (arr == null || arr.length == 0) return Collections.emptySet(); Map> indices = new TreeMap<>(); for (int i = 0; i < arr.length; i++) { if (!indices.containsKey(arr[i])) indices.put(arr[i], new TreeSet<>()); indices.get(arr[i]).add(i); } Set res = new LinkedHashSet<>(); for (Map.Entry> entry : indices.entrySet()) { int x = entry.getKey(); int y = k - x; if (x == y) { int size = entry.getValue().size(); if (size < 2) continue; Integer[] ind = entry.getValue().toArray(new Integer[size]); for (int j = 0; j < size - 1; j++) for (int m = j + 1; m < size; m++) res.add(String.format("[%d,%d]", ind[j], ind[m])); } else if (x < y && indices.containsKey(y)) for (int j : entry.getValue()) for (int m : indices.get(y)) res.add(String.format("[%d,%d]", j, m)); } return res; }