最近在准备面试，所以一直在刷算法题。然后越准备越发现不论是哪个公司，面试问的算法问题基本上都很水。我这里说的“很水”并不是所有的题我都能做出来，有些问题没见过类似的还是不太好想的。而是这些问题基本上都围绕着二分查找、链表、递归之类的在转圈圈。例如下面一些“水题”：
- 有一个有序数组，但是数组有可能被“右移”或者“左移”过，比如 [3, 5, 6, 7, 1, 2] 之类，要你写算法查找某个元素或者给出插入的下标。
- 有一个有序数组，除了某个元素外每个元素都恰好有 2 个，要你找出这个元素（要求 log n）。
- 有一个有序数组，里面元素有些有重复，给定一个元素，要你查找这个元素在这个数组里的范围（要求 log n，所以不要想着找到后前后遍历）。
- 有一个有序数组，里面大量元素是重复的，要你写一个算法，求出这个数组里一共有多少个不同的元素（要求 log n）。
诸如此类的“二分查找”的变种我随便就能说出一大堆。我实在是不明白老问这些问题有啥意义，考察你手写代码时的细心程度么？考察你代码写得规不规范么？众所周知，贪心、分治、回溯、分支限界以及动态规划是算法界的五大法宝，可是这些都在面试时很少涉及，尤其是动态规划。乃别告诉我写个二叉树遍历或者八皇后就叫做考察了回溯，连个剪枝都没有，乃确定这样的面试能够筛选出合适的人？
吐槽归吐槽，还是要按照实际情况来的。比如我一直想不通高考的古诗词默写有个毛意义，考察记忆力么？如果不是特别对古诗词感兴趣的，高考完后基本都会全忘掉（比如乃现在还能记得“路漫漫其修远兮，吾将上下而求索”的前一句么？），那和没有背有啥区别？不过乃也不能因为没有而不准备不是？
言归正传，这里老夫要记录一下 k-Sum 问题的解法。
这类问题是这样的，有一个数组里面有一堆元素（没排序），要你找出 k 个元素，使它们的和恰好等于 s。
1-“Sum”
特么一个元素还叫 Sum？老夫只是为了引出这个问题，也就是说我们要在这个数组里找出某个元素 s。
很显然只能暴力地去遍历整个数组，时间复杂度为 O(n)。如果先排序后二分，那么针对只需要搜索一次的情况就是 O(nlog n)了，得不偿失。
2-Sum
至于找出 2 个元素使它们的和等于 s，其实有个 O(n) 的算法。其实比较容易想到的是排序后用首位两个指针不断地移动，在查找过程中复杂度就是 O(n) 了，不过排序还需要 O(nlog n)的复杂度。
既然要 O(n)，那么只能空间换时间了（实际上 O(nlog n) 的排序也需要辅助空间）。知道可以用辅助空间后，那问题就很简单了，遍历到某个元素 a[i] 后只需要知道数组里有没有 s – a[i] 就可以了，显然用哈希表就能解决。
（用了这个 bug 一大堆的插件后，泛型的类型都丢了，而且有些显示不正常，凑合着看吧。）
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (hash.containsKey(target - nums[i])) {
return new int[] { hash.get(target - nums[i]), i };
}
hash.put(nums[i], i);
}
return null;
}要说对付这种很水的面试，哈希表是一个大神器。比如老夫以前面试时就遇到过这个问题的变种：
给你一个整型数组，任意取其中连续一段，比如 a[m .. n]，把这些元素进行“按位或”操作 a[m] | a[m + 1] | … | a[n]，其结果记为 k。问乃在这个数组中， k 一共有多少种不同的取值。
3-Sum
现在考虑三个元素情况。如果采用暴力搜索，那复杂度就是 O(n^3)，所以我们要找的方法就是低于这个复杂度的算法。回想一下我刚才在两个元素时提到的那个排序后用 O(n) 找出两个元素和为某一数值的算法，这里正好可以派上用场。
先把数组排序，枚举第一个元素 a[k]，那么接下来我们就要在 a[k + 1] .. a[n] 中找出和恰好为 s – a[k] 的元素了（乃说为啥不考虑 a[0].. a[k – 1] 之间的元素？特么枚举到 k 之前已经包括了啊）。接下来我们用两个指针 l 和 h 分别指向 k + 1 和 n 这两个位置，如果这两个指针指向的元素相加正好等于 s – a[k]，那么很好我们就找到了一种情况（不过别急着把循环 break 掉，因为还有可能有其他解）。如果大于 s – a[k] ，就把 h 往前移一个位置，由于数组是单调递增的，把 h 往前移后结果必然会减少或者不变。如果小于，则 l 往后移。
由于 l 和 h 最终会交汇，因此我们只需要枚举 n – k 次，另外我们还需要枚举第一个元素 n – 2 次，因此总的复杂度是 O(n^2)。
看似问题解决了，可是如果题目要求你找出不同的结果集呢（相同数组不同下标视为相同的结果）？此时我们就要把重复的结果过滤掉。在返回结果之前用暴力搜索过滤掉重复结果自然是可以（因为毕竟我们的复杂度已经是 O(n^2) 了），但实际上我们在枚举的过程中就能把重复的结果去掉。
在枚举第一个元素的时候，如果遇到与上一个相同的元素我们可以直接跳过。同样在 l 和 h 移动的过程中我们也需要跳过与上次相同的元素。但是要特别注意只有在找到结果后才跳过一样的元素，一定不能在没找到结果时就跳过重复的元素。比如如果我们有 [1, 1, 1, 3, 4]，我们要查找 2，如果一开始就跳过相同元素使 l 移动到了 3 的位置，那 1, 1 就找不到了。
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int l, h;
for (int i = 0; i + 2 < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int rest = -nums[i];
l = i + 1; h = nums.length - 1;
while (l < h) {
if (rest == nums[l] + nums[h]) {
result.add(Arrays.asList(nums[i], nums[l], nums[h]));
while (l < h && nums[l] == nums[l + 1]) l++;
while (l < h && nums[h] == nums[h - 1]) h--;
l++;h--;
} else if (nums[l] + nums[h] > rest) {
h--;
} else {
l++;
}
}
}
return result;
}问题变种：雨水问题
（问题来源：LeetCode 第 42 题）有一个凹凸不平的池子，每一块宽都为 1。池子两侧没有盖子而前后有盖子，如下图所示。现在下雨了，问这个池子能装多少水。
输入：一个数组 a[0..n]，a[i] 表示 坐标为 i 的区域高度为 a[i]。
输出：能装的水的面积（在这里看成是二维的）。
乃不妨自己先想想再看下面的解答。
————————————————————————————————————————
————————————————ＴＨＩＮＫＩＮＧ．．．—————————————
————————————————————————————————————————
其实这个问题和 k-Sum 关系不大，但是也可以用两个指针互相靠近就能搞定，有点类似上面的解法，所以我把它当成是“变种”问题。乃貌似不太服？怎 yan（和某个发音不标准的同事学的），乃打我呀！
以上面那张图为例，假如我们的指针 l 和 h 在 3 、7 这两个位置，也就是下面红框内的区域：
此时，雨水一定不能比左边的位置高，但是低于左边高度的区域一定能装雨水！也就是说，我们可以右边不动，移动左边的指针来统计雨水的面积，对于某个高度是 a[i] 的区域，它能装的雨水就是 a[l] – a[i]。那如果遇到了一个比 a[l] 高的位置怎么办呢？很简单，此时判断 a[i] 和 a[h] 哪个比较高，移动矮的那个就可以了！
至于由于池子左右没有板子，所以要过滤掉不能装水的地方，直到碰到递减的高度之前，都是装不了水的。
public int trap(int[] height) {
int v = 0;
if (height.length < 3) return 0;
int l = 0, r = height.length - 1;
while (l < height.length - 1 && height[l] < height[l + 1]) l++;
while (r > 0 && l < r && height[r] < height[r - 1]) r--;
if (l >= r) return 0;
while (l < r) {
int hl = height[l], hr = height[r];
if (height[l] <= height[r]) {
while (l < r && hl >= height[++l]) {
v += hl - height[l];
}
} else {
while (l < r && hr >= height[--r]) {
v+= hr - height[r];
}
}
}
return v;
}4-Sum
回到主题上，现在要找出 4 个元素和为 s，咋找？如果模仿 3-Sum 的做法，那我们就需要枚举前两个元素，复杂度是 O(n^3)，有没有更好的方法呢？
还记得我们做 2-Sum 吗？我们用了一个哈希表来判断有没有 s – a[i] 的元素。那我们就可以想到：如果把这 4 个元素两个两个一组，不就能用类似的办法了吗？所以我们可以想出如下算法：
- 枚举数组 a 中任意两个元素相加的所有可能性放到一个排好序的数组 S 中。由于一共有 n 个元素，枚举需要 O(n^2) 的复杂度，之后对这 n^2 的元素排序（注意！两两相加最多有 n^2 种结果），所以复杂度是 T(n^2*log (n^2)) = T(n^2*2*log n) = O(n^2*logn)。
- 接下来就容易了，遍历 S 中的每个元素，看看 S 中有没有 s – S[i] 就好了，如果有，组合一下就是结果。由于 S 是有序的，因此遍历时复杂度是 O(nlogn)。
因此总的复杂度是 O(n^2*logn) 了，比 O(n^3) 更优。
实际上，如果不对 S 进行排序而是放在哈希表中，那么复杂度就降到 O(n^2) 了。可是还有一个比较棘手的问题：如何去重以及自己和自己相加的情况。比如我们有 4 个 1，按照此办法我们会在和为 2 的位置记录多次 {1, 1} 元素对，此时我们需要对相同的元素对进行计数，否则就不能判断是不是能够 {1, 1} 和 {1, 1} 进行组合了。
k-Sum
推广到 K 个元素的情况。如果 K 为偶数，那么解法和 4-Sum 类似。
如果 K 为奇数，枚举第一个元素 a[i]，接下来按照偶数的情况查找 s – a[i] 就好了。