在一个数组中，给定targer，找到 n 个数使它们的和为target
比如数组为 [-4,-4,-3,-2,-1,0,1,2,3,4,4]
n = 2 时，target=0, 结果有 [-4,4] , [-3,3] .....
n = 3 时，target=0, 结果有 [-4,1,3] ,[-3,1,2]...
n = 4 时，target=1，结果有 [-4,-2,3,4]......
题目可以问有个种下标不同的组合方法，
也可以问有多少种数组元素不同的组合方法
两数之和
可以使用哈希表的方法来解决
记当前元素为 a ， 从头开始遍历 ，
- 如果哈希表中不存在 target - a 这个元素，将这个元素值座位 key，下标作为 value 加入到哈希表中
- 如果哈希表中存在 target - a 这个元素，那就是存在，返回两个元素的下标即可。
如果遍历到数组末尾都没有找到，那就代表没有
可以用排序加双指针的做法
先整体排序，然后一前一后两个指针进行遍历，方法和二分查找类似。
难度升级
nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。
比如说输入为 nums = [1,3,1,2,2,3], target = 4，那么算法返回的结果就是：[[1,3],[2,2]]。
对于修改后的问题，返回元素的值而不是对应索引并没什么难度，关键难点是现在可能有多个和为 target 的数对儿，还不能重复，比如上述例子中 [1,3] 和 [3,1] 就算重复，只能算一次。
对于上面提到的例子，因为问的是数组元素的值，可以先排序
排序后，【1，1，2，2，3，3】
因为要求对于同样的元素值组成结果集合只算做一次
利用双指针，在遍历过程中，逐步缩小两个指针的距离，如果指针相遇，且没有新的结果集合产生，那就代表着当前的元素是无法满足题目要求的，则从下一个元素开始寻找。
// 伪代码
// 先对数组排序
sort(nums);
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// 根据 sum 和 target 的比较，移动左右指针
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.add({lo, hi});
lo++; hi--;
}
}
return res;
}
这样做会把重复元素值的集合也加入到结果集中，所以在加入结果集的过程中就要想办法去重。
要么加入了结果集去重，要么加入前就去重，自己写一下就知道加入结果之后去重有多麻烦，所以这里采用加入前就合理去重，这也是一个比较通用的处理方案。
分析一下重复结果产生的原因发现，
【1，1，2，2，3，3】，target=4
出问题的地方在于 sum == target 条件的 if 分支，当给 res 加入一次结果后，lo 和 hi 不应该只改变 1，而应该跳过所有重复的元素
//伪代码
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// 记录索引 lo 和 hi 最初对应的值
int left = nums[lo], right = nums[hi];
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.add({left, right});
// 跳过所有重复的元素
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
这样就可以保证一个答案只被添加一次，重复的结果都会被跳过，可以得到正确的答案。不过，受这个思路的启发，其实前两个 if 分支也是可以做一点效率优化，跳过相同的元素
//伪代码
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.add({left, right});
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
return res;
三数之和
对于三数之和等于target，可以看做是一个给定数加上剩余的数中求两个数之和等于 target 减去给定数
public List<List<Integer>> threeSum( int[] nums ) {
List<List<Integer>> res = new ArrayList<>();
//排序先
Arrays.sort( nums );
// 以每个元素开始，找出后面是否有对应的两个数加起来等于0
for ( int i = 0; i < nums.length; i++ ) {
//target=0 时特殊操作，如果题目给了target那就没有此步
if ( nums[i] > 0 ) {
return res;
}
//这一步是去重，如果当前元素和上一个元素相等
// 那么对于同一个值的元素， 如果存在满足题目要求的另外两两个数，
///则一定与前一个数的结果集一样
if ( i > 0 && nums[i] == nums[i - 1] ) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while ( right> left ) {
int sum = nums[i] + nums[left] + nums[right];
if ( sum > 0 ) {
right--;
} else if ( sum < 0 ) {
left++;
} else if ( sum == 0 ) {
res.add( Arrays.asList( nums[i], nums[left], nums[right] ) );
while ( right > left && nums[right] == nums[right - 1] ) {
right--;
}
while ( right > left && nums[left] == nums[left + 1] ) {
left++;
}
right--;
left++;
}
}
}
return res;
}
四数之和
同理了，四个数简化为，给定一个数，在剩下的数中求三个数等于
target-给定的数
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//若当前数与前一个数相等，则跳过，因为结果集已经存在，
//或者必然不存在
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
//去重操作，原理同上
if (j > i + 1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
总结
两数之和中，暴力方法 O（n^2）
改用双指针，增加有限几个变量，降至一维
三数之和中，暴力方法 O（n^3）
改用多指针，增加有限几个变量，降至二维
四数之和中，暴力方法 O（n^4）
改用多指针，增加有限几个变量，降至三维
相当于使用多指针可以使原本的算法降低一个纬度。