算法复习笔记（六）

判断集合S中是否存在有两个其和等于x的元素

将S排序，借用辅助数组$S^{‘}=x-S$，合并$S^{‘}$和S

dutch national flag problem

红色球要全部在数组的左侧，白色球全部在中间，蓝色球全部在右侧，在遍历一次所有元素的情况下完成排序。

maximum-sub-segment-sum

针对每一个元素，有两个部分需要关注：① “过去部分” pre_sum；② “当前部分”nums[i]本身。有两种选择，① 加上pre_sum，本身融入到子串当中；② 以“当前部分”为子串起始位置，完全抛弃“过去部分”。

最大子矩阵

0, -2, -7,  0, 3
9,  2, -6,  2, 5
-4, 1, -4,  1, 6
-1, 8,  0, -2, 2

借鉴或者转为最大子序列，需要加一个辅助矩阵：全部子列和（totalColSum）

有了该辅助矩阵，我们就可以轻松求出指定列的子列和：

0, -2, -7, 0, 3
9, 0, -13, 2, 8
5, 1, -17, 3, 14
4, 9, -17, 1, 16

• 假如当前的子矩阵是{0,1}行，可直接得到子列和为9,0,-13,2,8
• 假如当前的子矩阵是{1,2}行，可通过totalColSum的第2行减去第0行的数据而得5,3,-4,3,11