《編程之美》讀書筆記10： 2.18 數組分割

如果直接遍歷，則至少要遍歷 Cr(n-1,2*n)次（Cr(m,n)為從n個數中取m個數的組合數），為了減少遍歷次數，可以先對數組排序。再將所有可能的組合大致分成幾組，每個組的數組和也是升序的，通過不斷的分組、查找，確定上下邊界條件，最終找到所求子數組。

如果數組各個元素均不相同，可以采用下面的算法：

先將數組{a_i}排序，并計算出各元素的總和的一半S(=Sum/2.0)，（對數組的劃分時，可以先選中a₀，再取n-1個數）。

假設T_i=sum(a₀+a_i+a_n+2+a_n+3…+a_2n-1) (0<i<=n+1) 則數組{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，假設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進行類似T_i的分析，找出下一個數。通過不斷的分組和查找和判斷，最終可以找到所求的n個數。

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

較小值   較大值

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個）

再重復上述操作。