从一个数组中找出一对元素，其总和等于一个给定的数字
给定n个整数的数组并给定一个数X，找出所有唯一的元素对（a，b），其总和等于X.
以下是我的解决scheme，它是O（nLog（n）+ n），但是我不确定它是否最优。
int main(void) { int arr [10] = {1,2,3,4,5,6,7,8,9,0}; findpair(arr, 10, 7); } void findpair(int arr[], int len, int sum) { std::sort(arr, arr+len); int i = 0; int j = len -1; while( i < j){ while((arr[i] + arr[j]) <= sum && i < j) { if((arr[i] + arr[j]) == sum) cout << "(" << arr[i] << "," << arr[j] << ")" << endl; i++; } j--; while((arr[i] + arr[j]) >= sum && i < j) { if((arr[i] + arr[j]) == sum) cout << "(" << arr[i] << "," << arr[j] << ")" << endl; j--; } } } # Let arr be the given array. # And K be the give sum for i=0 to arr.length - 1 do hash(arr[i]) = i // key is the element and value is its index. end-for for i=0 to arr.length - 1 do if hash(K - arr[i]) != i // if K - ele exists and is different we found a pair print "pair i , hash(K - arr[i]) has sum K" end-if end-for
这个解决scheme有三种方法：
设总和为T，n为数组的大小
方法1：
天真的做法是检查所有组合（nselect2）。 这个详尽的search是O（n 2 ）。
方法2：
更好的方法是对数组进行sorting。 这需要O（n log n）
然后对于数组A中的每个x，使用二进制search来查找Tx。 这将花费O（nlogn）。
所以整体search是O（n log n）
方法3：
最好的方法是将每个元素插入一个散列表（不需要sorting）。 这将O（n）作为定时插入。
那么对于每一个x，我们可以查找它的补码Tx，它是O（1）。
总的来说，这种方法的运行时间是O（n）。
你可以在这里参考。谢谢。
在Java中的实现：使用codaddict的algorithm（也许略有不同）
import java.util.HashMap; public class ArrayPairSum { public static void main(String[] args) { int []a = {2,45,7,3,5,1,8,9}; printSumPairs(a,10); } public static void printSumPairs(int []input, int k){ Map<Integer, Integer> pairs = new HashMap<Integer, Integer>(); for(int i=0;i<input.length;i++){ if(pairs.containsKey(input[i])) System.out.println(input[i] +", "+ pairs.get(input[i])); else pairs.put(k-input[i], input[i]); } } }
对于input= {2,45,7,3,5,1,8,9}以及Sum是10
输出对：
3,7 8,2 9,1
关于解决scheme的一些说明：
- 我们只在数组 – > O（n）时间迭代一次
- 在哈希插入和查找时间是O（1）。
- 总体时间是O（n），虽然它使用散列方面的额外空间。
解决scheme在Java。 您可以将所有的string元素添加到stringArrayList并返回列表。 在这里，我只是打印出来。
void numberPairsForSum(int[] array, int sum) { HashSet<Integer> set = new HashSet<Integer>(); for (int num : array) { if (set.contains(sum - num)) { String s = num + ", " + (sum - num) + " add up to " + sum; System.out.println(s); } set.add(num); } }
上）
def find_pairs(L,sum): s = set(L) edgeCase = sum/2 if L.count(edgeCase) ==2: print edgeCase, edgeCase s.remove(edgeCase) for i in s: diff = sum-i if diff in s: print i, diff L = [2,45,7,3,5,1,8,9] sum = 10 find_pairs(L,sum)
方法论：a + b = c，所以不是寻找（a，b），而是寻找a = c-b
这是一个解决scheme女巫考虑到重复条目。 它是写在JavaScript，并假定数组sorting。 该解决scheme运行在O（n）时间，除了variables之外不使用任何额外的内存。
var count_pairs = function(_arr,x) { if(!x) x = 0; var pairs = 0; var i = 0; var k = _arr.length-1; if((k+1)<2) return pairs; var halfX = x/2; while(i<k) { var curK = _arr[k]; var curI = _arr[i]; var pairsThisLoop = 0; if(curK+curI==x) { // if midpoint and equal find combinations if(curK==curI) { var comb = 1; while(--k>=i) pairs+=(comb++); break; } // count pair and k duplicates pairsThisLoop++; while(_arr[--k]==curK) pairsThisLoop++; // add k side pairs to running total for every i side pair found pairs+=pairsThisLoop; while(_arr[++i]==curI) pairs+=pairsThisLoop; } else { // if we are at a mid point if(curK==curI) break; var distK = Math.abs(halfX-curK); var distI = Math.abs(halfX-curI); if(distI > distK) while(_arr[++i]==curI); else while(_arr[--k]==curK); } } return pairs; }
我在一家大公司的面试中解决了这个问题。 他们拿走了，但不是我。 所以这里是给大家的。
从数组的两端开始，慢慢向内，确保数据重复（如果存在）。
它只计算对，但可以重做
- find对
- find对<x
- find对> x
请享用！
Python实现：
import itertools list = [1, 1, 2, 3, 4, 5,] uniquelist = set(list) targetsum = 5 for n in itertools.combinations(uniquelist, 2): if n[0] + n[1] == targetsum: print str(n[0]) + " + " + str(n[1])
输出：
1 + 4 2 + 3
C ++ 11，运行时复杂度O（n）：
#include <vector> #include <unordered_map> #include <utility> std::vector<std::pair<int, int>> FindPairsForSum( const std::vector<int>& data, const int& sum) { std::unordered_map<int, size_t> umap; std::vector<std::pair<int, int>> result; for (size_t i = 0; i < data.size(); ++i) { if (0 < umap.count(sum - data[i])) { size_t j = umap[sum - data[i]]; result.push_back({data[i], data[j]}); } else { umap[data[i]] = i; } } return result; }
这是在循环内使用二进制search实现的O（n * lg n）的实现。
#include <iostream> using namespace std; bool *inMemory; int pairSum(int arr[], int n, int k) { int count = 0; if(n==0) return count; for (int i = 0; i < n; ++i) { int start = 0; int end = n-1; while(start <= end) { int mid = start + (end-start)/2; if(i == mid) break; else if((arr[i] + arr[mid]) == k && !inMemory[i] && !inMemory[mid]) { count++; inMemory[i] = true; inMemory[mid] = true; } else if(arr[i] + arr[mid] >= k) { end = mid-1; } else start = mid+1; } } return count; } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; inMemory = new bool[10]; for (int i = 0; i < 10; ++i) { inMemory[i] = false; } cout << pairSum(arr, 10, 11) << endl; return 0; }
来自Codeaddict的很好的解决scheme。 我冒昧地在Ruby中实现它的一个版本：
def find_sum(arr,sum) result ={} h = Hash[arr.map {|i| [i,i]}] arr.each { |l| result[l] = sum-l if h[sum-l] && !result[sum-l] } result end
为了允许重复对（1,5），（5,1），我们只需要移除&& !result[sum-l]指令
这里有三种方法的Java代码：
1.使用Map O（n），HashSet也可以在这里使用。
2.对数组进行sorting，然后使用BinarySearch查找补充O（nLog（n））
3.传统的BruteForce两个循环O（n ^ 2）
public class PairsEqualToSum { public static void main(String[] args) { int a[] = {1,10,5,8,2,12,6,4}; findPairs1(a,10); findPairs2(a,10); findPairs3(a,10); } //Method1 - O(N) use a Map to insert values as keys & check for number's complement in map static void findPairs1(int[]a, int sum){ Map<Integer, Integer> pairs = new HashMap<Integer, Integer>(); for(int i=0; i<a.length; i++){ if(pairs.containsKey(sum-a[i])) System.out.println("("+a[i]+","+(sum-a[i])+")"); else pairs.put(a[i], 0); } } //Method2 - O(nlog(n)) using Sort static void findPairs2(int[]a, int sum){ Arrays.sort(a); for(int i=0; i<a.length/2; i++){ int complement = sum - a[i]; int foundAtIndex = Arrays.binarySearch(a,complement); if(foundAtIndex >0 && foundAtIndex != i) //to avoid situation where binarySearch would find the original and not the complement like "5" System.out.println("("+a[i]+","+(sum-a[i])+")"); } } //Method 3 - Brute Force O(n^2) static void findPairs3(int[]a, int sum){ for(int i=0; i<a.length; i++){ for(int j=i; j<a.length;j++){ if(a[i]+a[j] == sum) System.out.println("("+a[i]+","+a[j]+")"); } } } }
Java中一个简单的程序，用于具有独特元素的数组：
import java.util.*; public class ArrayPairSum { public static void main(String[] args) { int []a = {2,4,7,3,5,1,8,9,5}; sumPairs(a,10); } public static void sumPairs(int []input, int k){ Set<Integer> set = new HashSet<Integer>(); for(int i=0;i<input.length;i++){ if(set.contains(input[i])) System.out.println(input[i] +", "+(k-input[i])); else set.add(k-input[i]); } } }
一个简单的Java代码片段，用于打印下面的对：
public static void count_all_pairs_with_given_sum(int arr[], int S){ if(arr.length < 2){ return; } HashSet values = new HashSet(arr.length); for(int value : arr)values.add(value); for(int value : arr){ int difference = S - value; if(values.contains(difference) && value<difference){ System.out.printf("(%d, %d) %n", value, difference); } } }
Swift中的另一个解决scheme是：创build一个存储（sum – currentValue）值并将其与当前循环值进行比较的散列。 复杂度是O（n）。
func findPair(list: [Int], _ sum: Int) -> [(Int, Int)]? { var hash = Set<Int>() //save list of value of sum - item. var dictCount = [Int: Int]() //to avoid the case A*2 = sum where we have only one A in the array var foundKeys = Set<Int>() //to avoid duplicated pair in the result. var result = [(Int, Int)]() //this is for the result. for item in list { //keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5) if (!dictCount.keys.contains(item)) { dictCount[item] = 1 } else { dictCount[item] = dictCount[item]! + 1 } //if my hash does not contain the (sum - item) value -> insert to hash. if !hash.contains(sum-item) { hash.insert(sum-item) } //check if current item is the same as another hash value or not, if yes, return the tuple. if hash.contains(item) && (dictCount[item] > 1 || sum != item*2) // check if we have item*2 = sum or not. { if !foundKeys.contains(item) && !foundKeys.contains(sum-item) { foundKeys.insert(item) //add to found items in order to not to add duplicated pair. result.append((item, sum-item)) } } } return result } //test: let a = findPair([2,3,5,4,1,7,6,8,9,5,3,3,3,3,3,3,3,3,3], 14) //will return (8,6) and (9,5)
刚刚参加了这个问题的HackerRank，这里是我的“Objective C”解决scheme ：
-(NSNumber*)sum:(NSArray*) a andK:(NSNumber*)k { NSMutableDictionary *dict = [NSMutableDictionary dictionary]; long long count = 0; for(long i=0;i<a.count;i++){ if(dict[a[i]]) { count++; NSLog(@"a[i]: %@, dict[array[i]]: %@", a[i], dict[a[i]]); } else{ NSNumber *calcNum = @(k.longLongValue-((NSNumber*)a[i]).longLongValue); dict[calcNum] = a[i]; } } return @(count); }
希望它可以帮助别人。
Java中的实现：使用codaddict的algorithm：
import java.util.Hashtable; public class Range { public static void main(String[] args) { // TODO Auto-generated method stub Hashtable mapping = new Hashtable(); int a[]= {80,79,82,81,84,83,85}; int k = 160; for (int i=0; i < a.length; i++){ mapping.put(a[i], i); } for (int i=0; i < a.length; i++){ if (mapping.containsKey(k - a[i]) && (Integer)mapping.get(ka[i]) != i){ System.out.println(ka[i]+", "+ a[i]); } } } }
输出：
81, 79 79, 81
如果你想重复对（例如：80,80），那么只要从if条件中删除&&（Integer）mapping.get（ka [i]）！= i ，就可以了。
我可以做O（n）。 让我知道，当你想要的答案。 注意，它涉及到只需遍历数组一次，没有sorting，等等…我也应该提到它利用加法的交换性，不使用哈希，但浪费内存。
使用系统; 使用System.Collections.Generic;
/ *使用查找表存在O（n）方法。 这个方法是将这个值存储在一个“bin”中，如果这个值是一个合适的和值的候选者，那么这个值就可以很容易地被查find（例如，O（1））。
例如，
对于数组中的每个[k]，我们只需将它放在另一个数组中的位置x – a [k]。
假设我们有[0，1，5，3，6，9，8，7]和x = 9
我们创build一个新的数组，
索引值
9 - 0 = 9 0 9 - 1 = 8 1 9 - 5 = 4 5 9 - 3 = 6 3 9 - 6 = 3 6 9 - 9 = 0 9 9 - 8 = 1 8 9 - 7 = 2 7
那么唯一值得关注的是那些对新表有索引的人。
所以说，当我们到达9时，我们看看我们的新数组是否具有索引9 – 9 = 0。因为我们知道它包含的所有值将增加到9.（注意在这个原因中显而易见，只有1个可能一个，但它可能有多个索引值，我们需要存储）。
所以我们最终做的只是一次一次地移动数组。 因为加法是可交换的，我们将会得到所有可能的结果。
例如，当我们达到6时，我们得到新表中的索引为9 – 6 = 3。由于表包含该索引值，我们知道这些值。
这实际上是为了记忆而换取速度。 * /
namespace sum { class Program { static void Main(string[] args) { int num = 25; int X = 10; var arr = new List<int>(); for(int i = 0; i < num; i++) arr.Add((new Random((int)(DateTime.Now.Ticks + i*num))).Next(0, num*2)); Console.Write("["); for (int i = 0; i < num - 1; i++) Console.Write(arr[i] + ", "); Console.WriteLine(arr[arr.Count-1] + "] - " + X); var arrbrute = new List<Tuple<int,int>>(); var arrfast = new List<Tuple<int,int>>(); for(int i = 0; i < num; i++) for(int j = i+1; j < num; j++) if (arr[i] + arr[j] == X) arrbrute.Add(new Tuple<int, int>(arr[i], arr[j])); int M = 500; var lookup = new List<List<int>>(); for(int i = 0; i < 1000; i++) lookup.Add(new List<int>()); for(int i = 0; i < num; i++) { // Check and see if we have any "matches" if (lookup[M + X - arr[i]].Count != 0) { foreach(var j in lookup[M + X - arr[i]]) arrfast.Add(new Tuple<int, int>(arr[i], arr[j])); } lookup[M + arr[i]].Add(i); } for(int i = 0; i < arrbrute.Count; i++) Console.WriteLine(arrbrute[i].Item1 + " + " + arrbrute[i].Item2 + " = " + X); Console.WriteLine("---------"); for(int i = 0; i < arrfast.Count; i++) Console.WriteLine(arrfast[i].Item1 + " + " + arrfast[i].Item2 + " = " + X); Console.ReadKey(); } } }
这打印对，并避免重复使用按位操作。
public static void findSumHashMap(int[] arr, int key) { Map<Integer, Integer> valMap = new HashMap<Integer, Integer>(); for(int i=0;i<arr.length;i++) valMap.put(arr[i], i); int indicesVisited = 0; for(int i=0;i<arr.length;i++) { if(valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) { if(!((indicesVisited & ((1<<i) | (1<<valMap.get(key - arr[i])))) > 0)) { int diff = key-arr[i]; System.out.println(arr[i] + " " +diff); indicesVisited = indicesVisited | (1<<i) | (1<<valMap.get(key - arr[i])); } } } }
我绕过了一点点manuplation，只是比较指标值。 这小于循环迭代值（在这种情况下是我）。 这将不会打印重复的对和重复的数组元素也。
public static void findSumHashMap(int[] arr, int key) { Map<Integer, Integer> valMap = new HashMap<Integer, Integer>(); for (int i = 0; i < arr.length; i++) { valMap.put(arr[i], i); } for (int i = 0; i < arr.length; i++) { if (valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) { if (valMap.get(key - arr[i]) < i) { int diff = key - arr[i]; System.out.println(arr[i] + " " + diff); } } } }
在C＃中：
int[] array = new int[] { 1, 5, 7, 2, 9, 8, 4, 3, 6 }; // given array int sum = 10; // given sum for (int i = 0; i <= array.Count() - 1; i++) if (array.Contains(sum - array[i])) Console.WriteLine("{0}, {1}", array[i], sum - array[i]);
在python中
arr = [1, 2, 4, 6, 10] diff_hash = {} expected_sum = 3 for i in arr: if diff_hash.has_key(i): print i, diff_hash[i] key = expected_sum - i diff_hash[key] = i
一个解决scheme可以是这个，但不是优化（这个代码的复杂性是O（n ^ 2））：
public class FindPairsEqualToSum { private static int inputSum = 0; public static List<String> findPairsForSum(int[] inputArray, int sum) { List<String> list = new ArrayList<String>(); List<Integer> inputList = new ArrayList<Integer>(); for (int i : inputArray) { inputList.add(i); } for (int i : inputArray) { int tempInt = sum - i; if (inputList.contains(tempInt)) { String pair = String.valueOf(i + ", " + tempInt); list.add(pair); } } return list; } }
一个简单的python版本的代码，find一对零和，可以修改findk：
def sumToK(lst): k = 0 # <- define the k here d = {} # build a dictionary # build the hashmap key = val of lst, value = i for index, val in enumerate(lst): d[val] = index # find the key; if a key is in the dict, and not the same index as the current key for i, val in enumerate(lst): if (k-val) in d and d[k-val] != i: return True return False
函数的运行时复杂度为O（n），空间为O（n）。
public static int[] f (final int[] nums, int target) { int[] r = new int[2]; r[0] = -1; r[1] = -1; int[] vIndex = new int[0Xfff]; for (int i = 0; i < nums.length; i++) { int delta = 0Xff; int gapIndex = target - nums[i] + delta; if (vIndex[gapIndex] != 0) { r[0] = vIndex[gapIndex]; r[1] = i + 1; return r; } else { vIndex[nums[i] + delta] = i + 1; } } return r; }
https://github.com/clockzhong/findSumPairNumber
我在O（m + n）复杂度下为时间和内存空间做了这个。 我怀疑这是迄今为止最好的algorithm。
小于o（n）的解决scheme将是=>
function(array,k) var map = {}; for element in array map(element) = true; if(map(k-element)) return {k,element}
我的解决scheme – Java – 没有重复
public static void printAllPairSum(int[] a, int x){ System.out.printf("printAllPairSum(%s,%d)\n", Arrays.toString(a),x); if(a==null||a.length==0){ return; } int length = a.length; Map<Integer,Integer> reverseMapOfArray = new HashMap<>(length,1.0f); for (int i = 0; i < length; i++) { reverseMapOfArray.put(a[i], i); } for (int i = 0; i < length; i++) { Integer j = reverseMapOfArray.get(x - a[i]); if(j!=null && i<j){ System.out.printf("a[%d] + a[%d] = %d + %d = %d\n",i,j,a[i],a[j],x); } } System.out.println("------------------------------"); }
使用列表理解的Python解决scheme
f= [[i,j] for i in list for j in list if j+i==X];
O（N 2 ）
也给出了两个有序对 – （a，b）和（b，a）
Javascript解决scheme：
var sample_input = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]; var result = getNumbersOf(100, sample_input, true, []); function getNumbersOf(targetNum, numbers, unique, res) { var number = numbers.shift(); if (!numbers.length) { return res; } for (var i = 0; i < numbers.length; i++) { if ((number + numbers[i]) === targetNum) { var result = [number, numbers[i]]; if (unique) { if (JSON.stringify(res).indexOf(JSON.stringify(result)) < 0) { res.push(result); } } else { res.push(result); } numbers.splice(numbers.indexOf(numbers[i]), 1); break; } } return getNumbersOf(targetNum, numbers, unique, res); }
int [] arr = {1,2,3,4,5,6,7,8,9,0};
var z =（从arr中的a到arr中的arr，其中10 – a == bselectnew {a，b}）。
