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