在 n 個整數里，找出2個數相加等於 sum 的所有整數？

12-30

用stl實現，可以做到循環的時間複雜度為O(n)嗎？
補充：對空間複雜度沒有要求，可以用空間換時間！

先全放到 hash set 里，for (x : theSet) if (sum-x in theSet) print x, sum-x。

剛好 O(n)。

先把這些數排序，（不想麻煩可以直接調用庫，話說效率還是很不錯的），然後使用雙指針法，具體實現leetcode有這個原題，樓主可以去谷歌下！

既然是整數，可以使用Van Emde Boas tree，單次查找的時間從O(log N)降為O(log m)，m為整數的比特數，32或者64，可以認為是O(1)，而且不存在類似Hash碰撞的最壞情況。這樣一來不就是O(n)的複雜度了么。

import qualified Data.IntSet as IntSet

solve :: [Int] -&> Int -&> [(Int,Int)] solve lst sum = [(x,sum-x)|x&<-lst,IntSet.member (sum-x) set] where set = IntSet.fromList lst

===UPDATE===

@covariant在 @vczh答案的評論中指出{1,3,7}中找和為6的情況會出錯，感謝提出。這裡會輸出[(3,3)]。這裡如果限定是找出2個不相等的、相加等於sum的整數，那就需要額外加一道判定。如果是原list里出現1次就只能用1次，出現2次就只能用2次的話，需要把IntSet改為IntMap，記錄每個整數出現的次數，複雜度仍然不變。

int limit = 0;

for (int i = 0; i &< n; i++)

{

limit = limit &<= abs(array[i] * 2 - sum) ?abs(array[i] * 2 - sum)+1 : limit ;

}

vector& answer(limit,0);

for (int i = 0; i &< n; i++)

{

answer[abs(array[i] * 2 - sum)] ++ ;

}

for (int i = 0; i &{

if (answer[i] == 2)

cout &<&< (sum - i) / 2 &<&< " " &<&< (sum + i) / 2 &<&< endl;

}

前提是這n個數中最大的那個乘2後不會越界神馬的。

既然可以空間換時間，為什麼不開n bit數組？一遍標記一遍查詢。

修正下。

排序，如果都是整數，不用都是正的，且這些整數的正的最大值為k+，負的最小值為k-，定義kall = (k+) + (k-)，如果kall比n大不了多少，使用Counting Sort，可以做到O(n + kall)的複雜度。

1，先排序 O(n lg n)

2，然後二分查找 sum /2 的位置 ix O(lg n )

3，遍歷 ix 之前(或之後)的每一個數 x ，在二分查找 sum - x ，存在即 print O(n lg n)

排序之後頭尾倆指針，和大了就尾往前移，小了就頭往後移，掃到一個是一個， O(n)。

至於排序nlogn跑不掉的。

排序O(nlgn)，遍歷所有整數x看看n-x是不是在裡面O(nlgn)。

第二部隱約覺得可以前後掃描O(n)，不過一下子沒想起來。不過反正都要排序，比O(ngln)低應該很難。

===============================================

竟然對空間複雜度沒有要求啊，那就要求整數是int32，上64位系統，然後直接開大數組啊哈哈哈。因為int32的大小跟n沒關係，所以空間複雜度是O(1)，更低了，哈哈哈哈哈哈哈。

可以on，開n個線程

用bitmap最好

用整數最大值的內存位，對應整數存在的位為1，其他為0

遍歷整數for i in array（i對應的位肯定是打開的1），然後判斷sum-i對應的位是否打開即可

兩次遍歷+O(1)的判斷

線性排序一下比如計數排序、桶排序，O(n)

然後模仿快速排序的動作，兩個下標:

i=頭,j=尾

while(i&=0){

test=d[i]+d[j];

if test &> sum:

j--;

else if test& i++;

else

print d[i] and d[j]

}

為什麼要幫樓主寫作業

排序+頭尾指針，同理樓主可以考慮解決3個數，4個數，ksum

這不是leetcode上面的一道題的變形嘛。。

mulitMap的複雜度是O(nlgn)。。。

記得好像c++ primer第四版在講hash的時候有提過這個問題。

排序之後，使用雙標號i,j，假設使用升序，數組為a，長度為n，那麼i=0,j=n-1。

while(i&if(a[i]+a[j]& i++;

}

else if(a[i]+a[j]&>sum){

j--;

}

else{

將a[i],a[j]記錄；

i++;

j--;

}

因為有排序所以複雜度還是不能達到o(n)

hash之後搜索就可以了，不用排序，複雜度小於O(nlogn)