【leetcode】18. 四数之和(medium)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode】18. 四数之和(medium)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给你一个由 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
你可以按任意顺序返回答案。

思路：“XX之和”问题解法：排序+双指针。暴力法时间复杂度为 $O(n^4)$ ，使用双指针可以降至 $O(n^3)$ 。注意剪枝方法和去重方法。文章来源地址https://www.toymoban.com/news/detail-643438.html

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length < 4) return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            if(nums[i] > target && nums[i]>0) return res; //剪枝：如果第一个元素就大于target，那么就没有可行解
            if((i>0)&&(nums[i-1]==nums[i])) continue; // 去重a
            for(int j=i+1; j<nums.length-2; j++){
                if(nums[i]+nums[j]>target && nums[0]>0) return res; //剪枝
                if((j>i+1)&&(nums[j-1]==nums[j])) continue; //去重b
                int left = j+1;
                int right = nums.length-1;
                while(left < right){
                    long sum = (long)nums[i]+nums[j]+nums[left]+nums[right]; //溢出
                    if(sum == target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right && nums[left]==nums[left+1]) //去重c,left++不能越界
                            left++;
                        while(left<right && nums[right]==nums[right-1]) //去重d,right--不能越界
                            right--;
                        left++;
                        right--;
                    }
                    else if(sum > target)
                        right--;
                    else if(sum < target)
                        left++;
                }
            }
        }
        return res;
    }
}