Leetcode 18. 四数之和

1.题目基本信息

1.1.题目描述

给你一个由 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.2.题目地址

https://leetcode.cn/problems/4sum/description/

2.解题方法

2.1.解题思路

排序+双指针

2.2.解题步骤

第一步，边界条件判断，如果nums的长度小于4，则不可能组合成合法的组合，返回空数组

第二步，将nums进行升序排列，这里使用python的内置排序函数sort实现

第三步，遍历获取四个数字中的前两个数字。第一个数字遍历从下标0到下标length-4，记下标为i，第二个数字的遍历从下标i+1到下标length-3，记为j；为了防止出现重复的四数组合并减少遍历次数，当i大于0并且i处的值等于i-1处的值，可以直接跳到下一轮循环；如果i与后面相连的三个数的和大于target，则说明i及nums后面数字的组合的和都大于target，则可以直接退出该for循环；如果i处的值和nums最后三个数字的和小于target，则i和后面的数的组合的和都会小于target，跳过该轮循环遍历下一个i。同理，对j也做相同的处理

第四步，在遍历获取i和j后，对后两个数字进行双指针处理。初始化left和right指针为j+1和length-1。如果四个数字的和小于target，则需让组合的和增大，即让left+=1；如果四个数字的和大于target，则需要让和减小，即让right-=1；如果四个数字的组合等于target，则将组合加入到result数组中，同时值得注意的是为了防止出现重复数组被放到结果数组中，需要让left指针向右移，最终让left指向的值不等于刚才的值的位置，同理的也需要让right向左移直到指向与刚才不相等的值的位置

第五步，经过遍历后，所有非重复的四数组合都将被放到到result数组中，返回即可

3.解题代码

Python代码

class Solution:
    # 排序+双指针
    # 第一步，边界条件判断，如果nums的长度小于4，则不可能组合成合法的组合，返回空数组
    # 第二步，将nums进行升序排列，这里使用python的内置排序函数sort实现
    # 第三步，遍历获取四个数字中的前两个数字。第一个数字遍历从下标0到下标length-4，记下标为i，第二个数字的遍历从下标i+1到下标length-3，记为j；为了防止出现重复的四数组合并减少遍历次数，当i大于0并且i处的值等于i-1处的值，可以直接跳到下一轮循环；如果i与后面相连的三个数的和大于target，则说明i及nums后面数字的组合的和都大于target，则可以直接退出该for循环；如果i处的值和nums最后三个数字的和小于target，则i和后面的数的组合的和都会小于target，跳过该轮循环遍历下一个i。同理，对j也做相同的处理
    # 第四步，在遍历获取i和j后，对后两个数字进行双指针处理。初始化left和right指针为j+1和length-1。如果四个数字的和小于target，则需让组合的和增大，即让left+=1；如果四个数字的和大于target，则需要让和减小，即让right-=1；如果四个数字的组合等于target，则将组合加入到result数组中，同时值得注意的是为了防止出现重复数组被放到结果数组中，需要让left指针向右移，最终让left指向的值不等于刚才的值的位置，同理的也需要让right向左移直到指向与刚才不相等的值的位置
    # 第五步，经过遍历后，所有非重复的四数组合都将被放到到result数组中，返回即可
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        length=len(nums)
        if length<4:
            return []
        nums.sort()
        result=[]
        for i in range(length-3):
            if i>0 and nums[i]==nums[i-1]:
                continue
            if nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target:
                break
            if nums[i]+nums[length-3]+nums[length-2]+nums[length-1]<target:
                continue
            for j in range(i+1,length-2):
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                if nums[i]+nums[j]+nums[j+1]+nums[j+2]>target:
                    break
                if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                    continue
                left,right=j+1,length-1
                while left<right:
                    sum_=nums[i]+nums[j]+nums[left]+nums[right]
                    if sum_==target:
                        result.append([nums[i],nums[j],nums[left],nums[right]])
                        # 去除重复项
                        while left<right and nums[left]==nums[left+1]:
                            left+=1
                        left+=1
                        while left<right and nums[right]==nums[right-1]:
                            right-=1
                        right-=1
                    elif sum_<target:
                        left+=1
                    else:
                        right-=1
        return result

C++代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int length=nums.size();
        if(length<4){
            return {};
        }
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        for(int i=0;i<length-3;++i){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            if((long long) nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){
                break;
            }
            if((long long) nums[i]+nums[length-3]+nums[length-2]+nums[length-1]<target){
                continue;
            }
            for(int j=i+1;j<length-2;++j){
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                if((long long) nums[i]+nums[j]+nums[j+1]+nums[j+2]>target){
                    break;
                }
                if((long long) nums[i]+nums[j]+nums[length-2]+nums[length-1]<target){
                    continue;
                }
                int left=j+1,right=length-1;
                while(left<right){
                    long long sum_=(long long) nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum_==target){
                        result.push_back({nums[i],nums[j],nums[left],nums[right]});
                        while(left<right && nums[left]==nums[left+1]){
                            left++;
                        }
                        left++;
                        while(left<right && nums[right]==nums[right-1]){
                            right--;
                        }
                        right--;
                    }else if(sum_<target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return result;
    }
};

4.执行结果