A = {6,4,5,7,9,1,2}
和为10，那么两对数分别是 - {6,4} , {9,1}
我有两种解决方案。
sum-hash[i]。但是问题在于，虽然第二种解法只需要O(n)的时间，但同时也需要O(n)的空间。
所以，我想知道是否能够在O(n)的时间复杂度和O(1)的空间复杂度下完成此操作。这不是作业！
使用原地基数排序和 OP 的第一种解法，采用 2 个迭代器相向而行。
如果数组中的数字不是某种多精度数字，例如 32 位整数，可以使用几乎没有额外空间（每次通过 1 位）的方法在 2*32 次排序中将它们排序。或者使用 2*8 次排序和 16 个整数计数器（每次通过 4 位）。
两个迭代器解决方案的细节：
第一个迭代器最初指向已排序数组的第一个元素并向前移动。第二个迭代器最初指向数组的最后一个元素并向后移动。
如果迭代器引用的元素之和小于所需值，则将第一个迭代器推进。如果大于所需值，则将第二个迭代器推进。如果等于所需值，则成功。
只需要一次遍历，因此时间复杂度为 O(n)。空间复杂度为 O(1)。如果使用基数排序，整个算法的复杂度将保持不变。
如果您对相关问题感兴趣（涉及多于 2 个数字的总和），请查看“具有固定子集大小的总和子集”和“在数组中找到总和最接近给定数的三个元素”。
N log U位（最坏情况）或N log N位（对于均匀分布的数字和N < U的情况平均情况）。 - Evgeny Kluev[1]暴力解法
此算法非常简单。时间复杂度为O(N^2)。
[2]使用二分查找
使用二分查找来找到Sum-arr[i]与每个 arr[i]，时间复杂度可以降至 O(N*logN)。
[3]使用哈希
基于[2]算法，使用哈希，时间复杂度可降至O(N)，但此解决方案将增加O(N)的哈希空间。
[4]最优算法：
伪代码:
for(i=0;j=n-1;i<j)
if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);
或者
If a[M] + a[m] > I then M--
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.
这个问题已经完全解决了吗？并没有。如果数字是N，则此问题将变得非常复杂。
那么问题是：
如何找到给定数字的所有组合情况？
这是一个经典的NP-Complete问题，称为子集和问题。
要理解NP / NPC / NP-Hard，最好阅读一些专业书籍。
参考资料：
[1]http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2]http://en.wikipedia.org/wiki/Subset_sum_problem
for (int i=0; i < array.size(); i++){
int value = array[i];
int diff = sum - value;
if (! hashSet.contains(diffvalue)){
hashSet.put(value,value);
} else{
printf(sum = diffvalue + hashSet.get(diffvalue));
}
}
--------
Sum being sum of 2 numbers.
def check_sum_in_list(p_list, p_check_sum):
l_dict = {i: (p_check_sum - i) for i in p_list}
for key, value in l_dict.items():
if key in p_list and value in p_list:
return True
return False
if __name__ == '__main__':
l1 = [1, 3, 7, 12, 72, 2, 8]
l2 = [1, 2, 2, 4, 7, 4, 13, 32]
print(check_sum_in_list(l1, 10))
print(check_sum_in_list(l2, 99))
Output:
True
Flase
版本 2
import random
def check_sum_in_list(p_list, p_searched_sum):
print(list(p_list))
l_dict = {i: p_searched_sum - i for i in set(p_list)}
for key, value in l_dict.items():
if key in p_list and value in p_list:
if p_list.index(key) != p_list.index(value):
print(key, value)
return True
return False
if __name__ == '__main__':
l1 = []
for i in range(1, 2000000):
l1.append(random.randrange(1, 1000))
j = 0
i = 9
while i < len(l1):
if check_sum_in_list(l1[j:i], 100):
print('Found')
break
else:
print('Continue searching')
j = i
i = i + 10
Output:
...
[154, 596, 758, 924, 797, 379, 731, 278, 992, 167]
Continue searching
[808, 730, 216, 15, 261, 149, 65, 386, 670, 770]
Continue searching
[961, 632, 39, 888, 61, 18, 166, 167, 474, 108]
39 61
Finded
[Finished in 3.9s]
public void printPairsOfNumbers(int[] a, int sum){
//O(n2)
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if(sum - a[i] == a[j]){
//match..
System.out.println(a[i]+","+a[j]);
}
}
}
//O(n) time and O(n) space
Set<Integer> cache = new HashSet<Integer>();
cache.add(a[0]);
for (int i = 1; i < a.length; i++) {
if(cache.contains(sum - a[i])){
//match//
System.out.println(a[i]+","+(sum-a[i]));
}else{
cache.add(a[i]);
}
}
}
M是恒定的，并且数组中的条目为正数，则可以使用M/2指针(O(1)空间)在一次遍历(O(n)时间)中执行以下操作。这些指针标记为P1,P2,...,Pk，其中k=floor(M/2)。然后执行以下操作：for (int i=0; i<N; ++i) {
int j = array[i];
if (j < M/2) {
if (Pj == 0)
Pj = -(i+1); // found smaller unpaired
else if (Pj > 0)
print(Pj-1,i); // found a pair
Pj = 0;
} else
if (Pj == 0)
Pj = (i+1); // found larger unpaired
else if (Pj < 0)
print(Pj-1,i); // found a pair
Pj = 0;
}
}
你可以通过将索引存储为基数为N的数字来处理重复条目（例如两个6）。例如，对于M/2，您可以添加条件语句。
if (j == M/2) {
if (Pj == 0)
Pj = i+1; // found unpaired middle
else
print(Pj-1,i); // found a pair
Pj = 0;
}
但现在你有把这些“对”组合起来的问题。
Pj 应该更像 P[j] 吗？ - svickM是固定的，我有一个更简单的算法。在数组上进行M/2次遍历，在第一次遍历中查找1和M-1，在第二次遍历中查找2和M-2，以此类推，在O(NM) = O(N)时间内完成。 - Ali FerhatM是O(1)似乎有些作弊。如果M是O(1)，那么在数组中只会有O(1)个唯一值可以参与求和，因此你只需要花费O(n)的时间找到这些值，然后使用任何算法都将是O(1)的时间和空间复杂度。 - interjay function compareArraySums(array, compare){
var candidates = [];
function compareAdditions(element, index, array){
if(element <= y){
candidates.push(element);
}
}
array.forEach(compareAdditions);
for(var i = 0; i < candidates.length; i++){
for(var j = 0; j < candidates.length; j++){
if (i + j === y){
return true;
}
}
}
}
static void printpairs(int arr[],int sum)
{
// Declares and initializes the whole array as false
boolean[] binmap = new boolean[MAX];
for (int i=0; i<arr.length; ++i)
{
int temp = sum-arr[i];
// checking for condition
if (temp>=0 && binmap[temp])
{
System.out.println("Pair with given sum " +
sum + " is (" + arr[i] +
", "+temp+")");
}
binmap[arr[i]] = true;
}
}
// Main to test the above function
public static void main (String[] args)
{
int A[] = {1, 4, 45, 6, 10, 8};
int n = 16;
printpairs(A, n);
}
}
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
O(n)时间和O(1)空间结尾？ - greybeardhttps://github.com/clockzhong/findSumPairNumber
#! /usr/bin/env python
import sys
import os
import re
#get the number list
numberListStr=raw_input("Please input your number list (seperated by spaces)...\n")
numberList=[int(i) for i in numberListStr.split()]
print 'you have input the following number list:'
print numberList
#get the sum target value
sumTargetStr=raw_input("Please input your target number:\n")
sumTarget=int(sumTargetStr)
print 'your target is: '
print sumTarget
def generatePairsWith2IndexLists(list1, list2):
result=[]
for item1 in list1:
for item2 in list2:
#result.append([item1, item2])
result.append([item1+1, item2+1])
#print result
return result
def generatePairsWithOneIndexLists(list1):
result=[]
index = 0
while index< (len(list1)-1):
index2=index+1
while index2 < len(list1):
#result.append([list1[index],list1[index2]])
result.append([list1[index]+1,list1[index2]+1])
index2+=1
index+=1
return result
def getPairs(numList, target):
pairList=[]
candidateSlots=[] ##we have (target-1) slots
#init the candidateSlots list
index=0
while index < target+1:
candidateSlots.append(None)
index+=1
#generate the candidateSlots, contribute O(n) complexity
index=0
while index<len(numList):
if numList[index]<=target and numList[index]>=0:
#print 'index:',index
#print 'numList[index]:',numList[index]
#print 'len(candidateSlots):',len(candidateSlots)
if candidateSlots[numList[index]]==None:
candidateSlots[numList[index]]=[index]
else:
candidateSlots[numList[index]].append(index)
index+=1
#print candidateSlots
#generate the pairs list based on the candidateSlots[] we just created
#contribute O(target) complexity
index=0
while index<=(target/2):
if candidateSlots[index]!=None and candidateSlots[target-index]!=None:
if index!=(target-index):
newPairList=generatePairsWith2IndexLists(candidateSlots[index], candidateSlots[target-index])
else:
newPairList=generatePairsWithOneIndexLists(candidateSlots[index])
pairList+=newPairList
index+=1
return pairList
print getPairs(numberList, sumTarget)
我已经成功地使用Python实现了一种O(n+m)时间和空间成本的解决方案。
"m"表示这两个数字之和需要等于的目标值。
我相信这是最低成本的解决方案。Erict2k使用了itertools.combinations，与我的算法相比，它也会产生类似或更高的时间和空间成本。