18. 四数之和
18. 四数之和
分析
这道题跟 15. 三数之和 很像，跟 454. 四数相加 II 反而没什么关系
一开始的时候，我想参考 454. 四数相加 II 的写法，先通过记录数组中所有的两个组合的和，然后遍历这些和，同时在 HashMap 中查找 target-当前和
，来将四个指针的问题降维为两个指针的问题（还是 Hash 表），但是发现在去重问题上翻了车，始终无法实现输入 [2,2,2,2,2] 输出 [[2,2,2,2]]，因为我没有记录和出现的次数，而是去重了。
感觉思路又错了，最后看官方题解，居然在 15. 三数之和 的基础上再套一层 for 循环即：是三层 for 循环嵌套 + 双指针。
像这种从一个数组中找出几个元素进行组合，而且元素不能重复的题目，只能先排序然后用四个指针来遍历所有元素了，同时排除相邻元素相等的可能。只能这样做
思路：首先对数组进行排序，排序是为了方便检查重复组合，然后用 for 循环遍历所有元素，此时元素的索引为 h，然后再用一个 for 循环，索引为 i，i 从 h+1 开始，然后将 i+1 定义为 j 指针，为第三个元素，k 指针指向 nums 数组的最后一个元素，为第四个元素，h 和 i 固定，我们需要相向移动 k 和 j，来查找 nums[h]+nums[i]+nums[j]+nums[k] 和为 target 的所有组合，循环的执行条件是 j < k（不能相等，相等就重复了），如果小了，就像右移动 j，如果大了，就向左移动 k，如果和为 target，则记录元素组合，并同时移动 j 和 k。
然后就是这道题的重点，就是如何对重复组合去重，因为我们会对 nums 进行了排序，所以 nums 中的所有的重复元素都会放到一起，此时我们只需要对比指针跟其上一个位置的值是否相等即可，如果相等就跳过，就可以避免搜索出重复的四元组合。
- h 的去重，当 h>0 的时候，比较
nums[h]跟nums[h-1]是否相等，如果相等则跳过 - i 的去重，当 i>h+1 的时候，比较
nums[i]跟nums[i-1]是否相等，如果相等则跳过 - j 的去重，当
j>i+1的时候，比较nums[j]跟nums[j-1]是否相等，如果相等则跳过 - k 的去重，当
k<nums.length-1的时候，比较nums[k]跟nums[k+1]是否相等，如果相等则跳过
注意，因为我们做过 15. 三数之和，所以很多同学会下意识地在遍历 h 和 i 的时候加上 nums[h] > target 就跳过的逻辑，这是不对的，在 15. 三数之和 这道题中因为 target 值是 0，所以如果第一个元素 nums[i] 就大于 0，那么后面的元素肯定都大于 0，那三数之和就永远不可能为 0，所以这个时候可以直接跳过，尝试下一个元素。然而，如果 target 是小于 0 的（本题中 targe 是可能小于 0 的），你是不能因为 nums[i] 大于 targe 直接 continue 的，这是因为如果 target 小于 0，比如 -11，但是 nums[i] 是 -6，-6 大于 -11，但是后续的元素虽然比 nums[i] 大，但是也可能是负数，比如 -5，因此，元素之和依然是有可能等于 target 的。所以这里不能贸然加这样的逻辑。
此外，注意看本体的提示部分
-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
int 类型最大值是 20 多亿，也就是
此外，代码随想录 中还提到了各层循环的剪枝操作，这里就懒得记了。
三数之和的时间复杂度是
而且如果有五数之和、六数之和之类的题，也都是这类写法，这是因为如果题目要求组合中的所有元素都来自于一个数组，而且一个元素只能用一次，其实这个时候，你就只能用先排序然后相邻元素去重的方法了，除此之外没有别的办法可以保证这一点。至于结果去重，那都是额外的附加条件，决定了题目解法的，就是要求组合中的所有元素都来自于一个数组，而且一个元素只能用一次。这一点，我们在 15. 三数之和#简单总结 中也总结过
总结
1. 两数之和 和 454. 四数相加 II 是一类题目，用 Map 解题
15. 三数之和 和 18. 四数之和 是一类题目，是双指针题目
解题
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;
}
简化的写法，好记一些
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// System.out.println(Arrays.toString(nums));
for(int h=0;h<nums.length;h++){
if(h>0 && nums[h]==nums[h-1]){
continue;
}
for(int i=h+1;i<nums.length;i++){
if(i>h+1 && nums[i]==nums[i-1]){
continue;
}
int j = i+1,k=nums.length-1;
while(j<k){
if(j>i+1 && nums[j]==nums[j-1]){
j++;
continue;
}
if(k<nums.length-1 && nums[k]==nums[k+1]){
k--;
continue;
}
long sum = (long)nums[h]+(long)nums[i]+(long)nums[j]+(long)nums[k];
if(sum < target){
j++;
}else if(sum > target){
k--;
}else{
List<Integer> comb = new ArrayList<>();
comb.add(nums[h]);
comb.add(nums[i]);
comb.add(nums[j]);
comb.add(nums[k]);
result.add(comb);
j++;
k--;
}
}
}
}
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;
}