力扣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]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

解题方法

这个《四数之和》无非就是在《三数之和》的基础上加了一层循环，然后把和为零变成了和为target，可以看一下这篇三数之和的文章：三数之和 Java版本

代码

class Solution {
    //采用双指针的方法
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //定义需要返回的集合
        List<List<Integer>> res = new ArrayList<>();
        //对数组进行排序，然后就可以采用双指针的方法了
        Arrays.sort(nums);
        //找出需要直接返回的情况,因为nums已经从小到大排序完了，所以如果第一个元素就大于零并且大于target，则不可能找到结果了
        if(nums[0]>0&&nums[0]>target){
            return res;
        }

        for (int i = 0; i < nums.length; i++) {
            //先对第一个要加入的数去重，比如[-1,-1,-1,0,1,1],前三个-1没必要每次都作为四元组中的第一个元素测试一遍
            // 因为题目要求最后返回的结果是不重复的，所以这里就去重掉
            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 (left<right){
                    int sum=nums[i]+nums[j]+nums[left]+nums[right];
                    if (sum>target){
                        right--;
                    } else if (sum < target) {
                        left++;
                    }else {
                        //sum==target的情况，找到一个符合的四元组
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        //对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;
    }
}