LeetCode每日一题，四数之和

题目

四数之和

https://leetcode-cn.com/problems/4sum/

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

难度：中等

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + 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 = [], target = 0
输出：[]

提示：

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

Solution

双指针解法

解题思路

题目条件

跟昨天写的三数之和差不多，唯一不同的点在于，这题求得是四数之和，趁热打铁，还是按照之前的三数之和的思路

暴力解法我就不讲了，直接多重FOR循环遍历求值即可，找到小于当前最小值的就替换，这个方案在三数之和就超时了，四数就不用想了

还是使用之前双指针的方式

• 我们先将nums进行从小到大的排序，对排序后的数组循环遍历，
• 不同的是，四数比之前的三数多了一数，这多的一数我们通过再增加一层FOR循环来实现即可
• 使用I和J分别表示第一层和第二层循环
• 使用双指针分别指向当前nums[j]的右侧和nums数组的最右侧
• 计算 nums[i] + nums[i] + nums[left] +nums[right] 的值
  • nums[i] + nums[i] + nums[left] +nums[right] > target，当前总值大于target值 ，在上一步已经进行了由小到大的排序，则需要Right的指针左移`
  • nums[i] + nums[i] + nums[left] +nums[right] - target = 0
    • 记录到最终结果中
    • 判断下一个Left OR Right是否相等，相等则跳过，去重，防止重复
  • nums[i] + nums[i] + nums[left] +nums[right]，当总值小于target值，则需要Left的指针右移
• 当Left == RIght 时，遍历终止，进入下一个i的遍历查找

image-20210424103626024

CODE

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //最终结果
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        //第一层i
        for(int i=0; i < len-3 ; i++){
            //第一层如果重叠的话直接跳过，i>0,防止第一次遍历就跳过了,同时使用i-1，防止数组越界，比如[1,1,2,3,4]，第二个1就会被跳过
            if(i>0&&nums[i]==nums[i-1]) continue;
            //第二层j
            for(int j=i+1;j<len-2;j++){
                //第二层如果重叠的话直接跳过，这里需要判断j>i+1,防止第一次遍历就跳过了，j-1防止数组越界，[1,2,2,3,4]，第二个2就会被跳过
                 if(j>i+1&&nums[j]==nums[j-1]) continue; 
                //左指针
                int left = j+1;
                //右指针
                int right = len-1;
                //左指针<右指针
                while(left < right){
                    //总值大于target，右指针左移
                    if(nums[i]+nums[left]+nums[right]+nums[j]>target){
                        right--;
                    //总值小于target，左指针右移
                    }else if(nums[i]+nums[left]+nums[right]+nums[j]<target){
                        left++;
                    }else{
                        //相等则添加到结果中
                        list.add(Arrays.asList(nums[i],nums[left],nums[right],nums[j]));
                        //重复的left值，直接left右移 
                        while(left < right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        //重复的right值，直接right左移1
                        while(left < right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return list;
    }
}

复杂度

• 时间复杂度：O(N^3)

结果

• 执行用时：24 ms, 在所有 Java 提交中击败了25.09%的用户

  内存消耗：38.8 MB, 在所有 Java 提交中击败了59.82%的用户

LeetCode名句

如果暴力不是证明自己有多蠢，那将毫无意义