18. 四数之和
18. 四数之和
分析
这个题跟 1. 两数之和、15. 三数之和 才是一样的，跟 454. 四数相加 II 反而没什么关系
一开始的时候，我想参考 454. 四数相加 II 的写法，先通过记录数组中所有的两个组合的和，然后遍历这些和，同时在 HashMap 中查找 target-当前和
，来将四个指针的问题降维为两个指针的问题（还是 Hash 表），但是发现在去重问题上翻了车，始终无法实现输入 [2,2,2,2,2] 输出 [[2,2,2,2]]，因为我没有记录和出现的次数，而是去重了。
感觉思路又错了，最后看官方题解，居然在 15. 三数之和 的基础上再套一层 for 循环即：是三层 for 循环嵌套 + 双指针。
15. 三数之和 的双指针解法是一层 for 循环 num[i] 为确定值，然后循环内有 left 和 right 下标作为双指针，找到 nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层 for 循环 nums[a] + nums[b] 为确定值，依然是循环内有 left 和 right 下标作为双指针，找出 nums[a] + nums[b] + nums[left] + nums[right] == target 的情况，三数之和的时间复杂度是
而且如果有五数之和、六数之和之类的题，也都是这类写法，好吧，挺无聊的。
这是因为如果题目要求组合中的所有元素都来自于一个数组，而且一个元素只能用一次，其实这个时候，你就只能用先排序然后双指针的方法了，除此之外没有别的办法可以保证这一点。至于结果去重，那都是额外的附加条件，决定了题目解法的，就是要求组合中的所有元素都来自于一个数组，而且一个元素只能用一次。这一点，我们在 15. 三数之和#简单总结 中也总结过
此外，注意看本体的提示部分
-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
int 类型最大值是 20 多亿，也就是，而单个元素最大就可能有 ，也就是说四个元素的和有可能超过 int 的最大值，因此需要用 long 类型来保存四个元素得和，这应该是这个题最大的难点了，哈哈哈
此外，代码随想录 中还提到了各层循环的剪枝操作，这里就懒得记了。
此外还有一些跟 15. 三数之和 相比不一样的点- 15. 三数之和 中，最外层循环中，如果
nums[i]大于 target 也就是 0，可以直接俄 break，是因为这个 target 大于等于 0，你是可以这样直接跳出来的，但是如果 target 是小于 0 的，你是不能因为nums[i]大于 targe 直接 break 的，这是因为如果 target 小于 0，比如 -11，但是nums[i]是 -5，-5 大于 -11，但是后续的元素也可能是负数，比如 -6，因此，当你不确定 target 大于等于 0 的时候，不要加这个判断。
解题
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
// 必须要先排序
Arrays.sort(nums);
for(int a=0;a<nums.length;a++){
if(a>0&&nums[a]==nums[a-1]){
continue;
}
// 第二层循环从第一个指针的下一个元素开始
for(int b=a+1;b<nums.length;b++){
if(b>a+1&&nums[b]==nums[b-1]){
continue;
}
int left = b+1,right=nums.length-1;
while(left<right){
// 避免四数之和溢出
long sum = (long)nums[a]+(long)nums[b]+(long)nums[left]+(long)nums[right];
if(sum<target){
left++;
}else if(sum>target){
right--;
}else{
List<Integer> pairs = new ArrayList<>();
pairs.add(nums[a]);
pairs.add(nums[b]);
pairs.add(nums[left]);
pairs.add(nums[right]);
result.add(pairs);
while( left+1<right && nums[left]==nums[left+1]){
left++;
}
while( left<right-1 && nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}
}
}
}
return result;
}
参考 15. 三数之和 的另一种判断 left 和 right 重复的解法
public List<List<Integer>> fourSum(int[] nums, int target) {
// 三数之和的升级版
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1, right = nums.length - 1;
// 用于去重
Integer leftPreVal = null;
Integer rightPreVal = null;
// 这个区间必须包含两个值，因此left必须小于right，保证这个区间有两个值
while (left < right) {
long nowSum = (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right];
if (nowSum < target) {
left++;
} else if (nowSum > target) {
right--;
} else {
if ((leftPreVal == null && rightPreVal == null)
|| (leftPreVal != nums[left] && rightPreVal != nums[right])) {
List<Integer> combination = new ArrayList<>();
combination.add(nums[i]);
combination.add(nums[j]);
combination.add(nums[left]);
combination.add(nums[right]);
result.add(combination);
leftPreVal = nums[left];
rightPreVal = nums[right];
}
right--;
left++;
}
}
}
}
return result;
}