《編程之美》讀書筆記10： 2.18 數(shù)組分割
如果直接遍歷，則至少要遍歷 Cr(n-1,2*n)次（Cr(m,n)為從n個數(shù)中取m個數(shù)的組合數(shù)），為了減少遍歷次數(shù)，可以先對數(shù)組排序。再將所有可能的組合大致分成幾組，每個組的數(shù)組和也是升序的，通過不斷的分組、查找，確定上下邊界條件，最終找到所求子數(shù)組。
如果數(shù)組各個元素均不相同，可以采用下面的算法：
先將數(shù)組{ai}排序，并計算出各元素的總和的一半S(=Sum/2.0)，（對數(shù)組的劃分時，可以先選中a0，再取n-1個數(shù)）。
假設Ti=sum(a0+ai+an+2+an+3…+a2n-1) (0<i<=n+1) 則數(shù)組{Ti}也是升序。如果Tn+1<=S則Tn+1即為所求，如果存在Ti=S，則Ti即為所求。否則，可以通過二分法找到唯一的i、j使得Ti<S<Tj，（選中a0和aj），記錄Ti，假設Ri=sum(a0+aj+ai+an+3+an+4…+a2n-1) (j<i<=n+2)，則Tj=Rn+2，比較Ti、Rj+1、Rn+2，再對Ri進行類似Ti的分析，找出下一個數(shù)。通過不斷的分組和查找和判斷，最終可以找到所求的n個數(shù)。
例如：長度為8的數(shù)組：共有35種組合，對每種組合的子數(shù)組和，可以劃分到幾個區(qū)間：(下面的0123表示取a0+a1+a2+a3)
較小值 較大值
0123 —— 0167 （共15個）
0234 —— 0267 （共10個）
0345 —— 0367 （共6個）
0456 —— 0467 （共3個）
0567 —— 0567 （共1個）
(各個較大值不必計算，它們間必然只有一個數(shù)不同（并且這個不同的數(shù)在升序數(shù)列中的位置是連續(xù)的），查找S在哪兩個較大值之間，可以用S減去相同的數(shù)的和，得到的差去指定的范圍（不同的那個數(shù)的位置范圍）進行二分查找。)
由于數(shù)組是升序，數(shù)組元素各不相同，右邊的“較大值”都是升序排列且不會重復。利用數(shù)組和的一半S進行查找，如果S在0267和0367之間。只要記錄0267，并在適當時候判斷該記錄是否是所求的，展開0345——0367的6個數(shù)，
0345 —— 0347（共3個）
0356 —— 0357（共2個）
0367 —— 0367（共1個）
再重復上述操作。