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