Sum类的题目一般这样：
input: nums[], target
output: satisfied arrays/ lists/ number
拿到题目，首先分析：
1. 是几个数的sum
2. sum是要求等于target还是小于还是大于还是closest
3. 返回的是原数组下标还是其他
对于这类题目，我们经常用双指针的方法。即排序后，左指针指向起点，右指针指向终点。
- 如果sum等于target，加入结果／总数目＋1
- 如果sum大于target，右指针左移
- 如果sum小于target，左指针右移
还有些情况下，我们需考虑去重。去重有两种方法：
- 利用HashSet预先存下满足条件的值
- 指针移动去重
第一种方法由于常常需要更多的空间，所以不太建议。
第二种方法的模板是：先判断值，再去重。（去重是当前的element和它前一个element比较）
这里给出一个 n Sum 的模板
public class Solution {
public void nSum(int[] nums, int target) {
// Check whether input is valid
if (nums == null || nums.length < n) {
return;
}
// Sort input array
Arrays.sort(nums);
// Fix one parameter
int length = nums.length;
for (int i = 0; i < length - n + 1; i++) {
// Avoid duplicate 1
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Fix more parameters
...
// Until two parameters left
// start and end are decided by innerest parameter value
int left = start;
int right = end;
while (left < right) {
int sum = nums[i] + .. + nums[left] + nums[right];
if (sum == target) {
// Some action
left++;
right--;
// Avoid duplicate 2
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < target) {
left++;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
} else {
right--;
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
}
}
Example:
以下是模板的变型问题：
1. 要返回原数组的下标。
这种情况下就不太好排序，因为排序会改变数组下标。
一般用HashMap做。
Example:
2. 返回所有满足小于target的组合的数目
Example:
3. 要求是closest
Example:
4. 利用HashMap化为2Sum问题
Example: