1樓：
先按照奇偶性，再由小到大，把S拆分為S1(奇數)+S2(偶數)
S1=S2=
如果a(L)>.b(L) ---- A
技巧性的從S1和S2中各抽取1個數，相加，判斷是否等於a(L)。如果都不等，則從 S1中捨棄a(L),即S發生了優化。回到 A或者B.
如果 a(L)<.b(L) ----B
技巧性的從S1中抽取2個數，相加，判斷是否等於b(L)。如果都不等，技巧性的從S2中抽取2個數，相加，判斷是否等於b(L)。如果都不等，則從 S2中捨棄b(L)，即S發生了優化。
回到 A或者B.
如果S含小數，
按照奇偶性和整數性，由小到大，把S拆分為S1(奇數)+S2(偶數) +S3(帶小數)
【若有必要，則更進一步，S3可細分為（奇數+小數）和（偶數+小數）2個集合】
S3=如果a(L)>.b(L) 且a(L)>.c(L) ---- A
技巧性的從S1和S2中各抽取1個數，相加，判斷是否等於a(L)。如果都不等，則技巧性的從S3中抽取2個數相加。如果都不等，則從 S1中捨棄a(L)。回到 A.
.......
顯然的，這種演算法，不需要遍歷所有的可能，因為人腦已經把至少一半的情況排除了。|S|的平方根。 @Chao Xu
2樓：
作為乙個從沒接觸過演算法理論的渣渣，竟然有點看懂 Chao Xu 博士的方法了。簡而言之是不是這樣的：
想要求集合 S =｛a1,a2,a3,a4,a5……｝中有沒有能滿足形如a[i]+a[j]=a[k]的，那就把S的相反數也考慮進來 -S = ，看看有沒有能滿足a[i]+a[j]+(-a[k])=0的。但是呢，又擔心，萬一(-a[k])也出現在集合S裡，或者a[i],a[j]也出現在集合-S中怎麼辦？那就把集合S和集合-S拉遠，拉得非常非常遠，以至於在同乙個集合中絕對不會出現三者相加=0的情況。
也就是上面的構建集合+S和-S。
不過因為我不懂嘛，所以想問一下：這樣真的可以減輕計算機的負擔麼？
3樓：「已登出」
更新:4/4/2014. 似乎http://
arxiv.org/abs/1404.0799
好像真存在更小演算法複雜度的演算法了... 我還沒看這個文章有時間看一下...
這個問題是 3SUM-hard . 如果你能給出在real RAM上的演算法(注意是小o不是大O), 則你就解決了幾十年來的未解問題, 整個計算幾何領域的一堆演算法會因此提速.
所以如果這個是面試題的話, 到了就可以停止了.
3SUM-hard的證明:
3SUM問題: 給有n個整數的集合S, 求是否存在x,y,z屬於S, 使得x+y+z=0.
我們將3SUM問題歸約到提問者的問題中.
讓.把+S和-S存到陣列a裡面. (這裡用的是這裡面加減的定義Arithmetic combinatorics).
存在a[i]+a[j] = a[k]有且僅有x+y+z = 0. x,y,z屬於S.
如果存在a[i]+a[j]=a[k], 則只有一種可能:
a[i]-m,a[j]-m屬於S, a[k]-2m屬於-S.
讓x=a[i]-m, y=a[j]-m, -z= a[k]-2m.
則x+y= -z, x+y+z=0.
如果存在x,y,z in S, 使得x+y+z = 0, 則存在i,j,k,使得
a[i]-m = x, a[j]-m = y, a[k]-2m = -z.
a[i}+a[j]-a[k]=0
a[i}+a[j] = a[k]
所以我們用O(n)的時間將3SUM問題歸約到了提問者的問題, 則提問者的問題是3SUM-hard的.
4樓：知三叉乎
列舉k是必須的，於是改變了問題給定乙個sum，判斷是否有a[i] + a[j] = sum.
這是個經典的2sum問題，自己上網查。
5樓：
1， Lower bound 一定是 O(n^2), 因為有約 nC2 種組合。
2， O(n^2) 可以是空間複雜度，那就是用table或者hash table預存；也可以是運算複雜度，那基本就是暴力算，可以優化，但是貌似沒有顯著提公升，因為O(n^2) 擺在那了；
3，拋磚引玉，我能想到的是O(n^2) 的preprocessing time, O(n) 的空間複雜度以及 O(nlogn) 的query time
給定乙個指標，如何判斷這個指標是否已經指向乙個合法的物件？
貓之公爵公之貓 請參考qpointer的實現。一般來說都是智慧型指標加一種檢驗實現的吧。純粹的裸指標。64位系統因為指標沒用完，可以在這裡做手腳 悽臨雨 系統給了判定乙個記憶體位址 長度，能否讀寫的函式，比如windows可以Virtualquery IsValidPtr。Linux我查了，有msy...
C 如何實現乙個給定維度的多維變長陣列型別
Github上有類似的專案 head only庫 給 dynarray 做了些修補和擴充套件，現在還能用，或許可以滿足題主的要求。首先是這個，出現得比較早，就叫做 dynarray Robbepop dynarray 基本能滿足需求，只要不使用自定義分配器 allocator 的話。如果要用自定義分...
乙個長度為n的整數陣列，是否有演算法可以在O n 的時間複雜度內，求出元素兩兩之差的最小值？
有。這是2D closest pair problem的乙個特殊情況，用隨機增量演算法可以做到期望O n 複雜度。注意這不違反高票答案提到的lower bound，因為用到了hashing。 先使用線性時間複雜度演算法進行排序，然後對有序陣列掃瞄一遍即可。ps 需要陣列中的數的絕對值的上界存在，在實...