聖地亞歌

Leetcode P0018"4Sum" 题解

2020/08/18 Leetcode

博文中会简要介绍Leetcode P0018题目分析及解题思路。

“4Sum”是”3Sum”的一道衍生题，这道题也可以划归为”kSum”这样的原型。这道题考察的核心是双指针和指针移动的边界条件。

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

这道题的思路和p00015的思路基本一致。我们可以得出以下边界条件：

    sum4 = nums[left]+nums[leftMed]+nums[rightMed]+nums[right]

    fix left;
        fix leftMed;
        if sum4 > target
            move right; right指针指向的是最大值，由于数组排序，right右边的一定更大，所以左移
        else if sum3 < target
            move rightMed; 理由同上但相反
        else
            record;

            move rightMed;
            move right; 这两个指针的相向移动是思路的核心，要强调，移动不能交错，移动需要保证结果去重

        move leftMed;
    move left;

以下是Java的题解代码实现。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) 
            return new ArrayList<>();
        
        Arrays.sort(nums);
        List<List<Integer>> quadruplets = new ArrayList<>();
        for (int left=0; left<nums.length-3; ++left) {
            if (left > 0 && nums[left] == nums[left-1])
                continue;
            
            for (int leftMed=left+1; leftMed<nums.length-2; ++leftMed) {
                if (leftMed > left+1 && nums[leftMed] == nums[leftMed-1])
                    continue;
                
                int rightMed = leftMed+1, right = nums.length-1, occupied = nums[left]+nums[leftMed];
                while (rightMed < right) {
                    int sum4 = nums[rightMed]+nums[right]+occupied;
                    
                    if (sum4 < target)
                        ++rightMed;
                    else if (sum4 > target)
                        --right;
                    else {
                        quadruplets.add(Arrays.asList(new Integer[] {nums[left], nums[leftMed], nums[rightMed], nums[right]}));
                        
                        ++rightMed;
                        while (rightMed < right && nums[rightMed] == nums[rightMed-1])
                            ++rightMed;
                        
                        --right;
                        while (right > rightMed && nums[right] == nums[right+1])
                            --right;
                    }
                }
            }
        }
        
        return quadruplets;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4) 
            return vector<vector<int>>();
        
        sort(nums.begin(), nums.end());
        vector<vector<int>> quadruplets;
        for (int left=0; left<nums.size()-3; ++left) {
            if (left > 0 && nums[left] == nums[left-1])
                continue;
            
            for (int leftMed=left+1; leftMed<nums.size()-2; ++leftMed) {
                if (leftMed > left+1 && nums[leftMed] == nums[leftMed-1])
                    continue;
                
                int rightMed = leftMed+1, right = nums.size()-1, occupied = nums[left]+nums[leftMed];
                while (rightMed < right) {
                    int sum4 = occupied+nums[rightMed]+nums[right];
                    
                    if (sum4 > target)
                        --right;
                    else if (sum4 < target)
                        ++rightMed;
                    else {
                        quadruplets.push_back({nums[left], nums[leftMed], nums[rightMed], nums[right]});
                        
                        ++rightMed;
                        while (rightMed < right && nums[rightMed] == nums[rightMed-1])
                            ++rightMed;
                        
                        --right;
                        while (right > rightMed && nums[right] == nums[right+1])
                            --right;
                    }
                }
            }
        }
        
        return quadruplets;
    }
};

Search

    Table of Contents