《编程之美》读书笔记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个）
再重复上述操作。