四数之和-力扣18-java排序+双指针

一、题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n

a、b、c 和 d 互不相同

nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0

输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8

输出：[[2,2,2,2]]

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/4sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、运行结果

三、解题思路

这题的整体思路和三数之和的思路是一致的，也是采用先排序，然后用双指针的方式。三数之和可以思路课可以参考另一篇博文：https://blog.csdn.net/LJH132465/article/details/129003854

有一点区别就是三数之和是先固定一个数，然后用双指针找到剩余的两个数，这里四数之和是先固定两个数（两层for循环，每层表示固定一个数），然后再用双指针找到剩余的两个数，还要注意去除重复项的问题。

四、AC代码

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {int len = nums.length;List<List<Integer>> ans = new ArrayList<>();if(len < 4) return ans;Arrays.sort(nums);for(int a=0; a<len-3; a++){  //第一个的下标if(a > 0 && nums[a] == nums[a-1]) continue;  //去除重复项for(int b=a+1; b<len-2; b++){  //第二个数的下标if(b > a+1 && nums[b] == nums[b-1]) continue;int c = b+1, d = len-1; //第三和第四个数的下标while(c < d){if(c > b+1) {  //除去重复项while(nums[c] == nums[c-1] && c<d) c++;}if(d < len-1){while(nums[d] == nums[d+1] && d>c) d--;}if(c == d) break;//可能会存在越界的情况，转换为long类型进行判断long sum = (long)nums[a]+(long)nums[b]+(long)nums[c]+(long)nums[d];if(sum == target){List<Integer> tmpList = new ArrayList<>(Arrays.asList(nums[a],nums[b], nums[c], nums[d]));ans.add(tmpList);c++; d--;} else if(sum > target)  d--;else c++;}}}return ans;}
}