《編程之美》讀書筆記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ù)組{a_i}排序，并計(jì)算出各元素的總和的一半S(=Sum/2.0)，（對數(shù)組的劃分時(shí)，可以先選中a₀，再取n-1個(gè)數(shù)）。

假設(shè)T_i=sum(a₀+a_i+a_n+2+a_n+3…+a_2n-1) (0<i<=n+1) 則數(shù)組{T_i}也是升序。如果T_n+1<=S則T_n+1即為所求，如果存在T_i=S，則T_i即為所求。否則，可以通過二分法找到唯一的i、j使得T_i<S<T_j，（選中a₀和a_j），記錄T_i，假設(shè)R_i=sum(a₀+a_j+a_i+a_n+3+a_n+4…+a_2n-1) (j<i<=n+2)，則T_j=R_n+2，比較T_i、R_j+1、R_n+2，再對R_i進(jìn)行類似T_i的分析，找出下一個(gè)數(shù)。通過不斷的分組和查找和判斷，最終可以找到所求的n個(gè)數(shù)。

例如：長度為8的數(shù)組：共有35種組合，對每種組合的子數(shù)組和，可以劃分到幾個(gè)區(qū)間：(下面的0123表示取a₀+a₁+a₂+a₃)

較小值   較大值

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ù)上述操作。