Problem

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.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

K-Sum问题. 给定N个整数的数组以及一个整数target. 在数组中查找4个数a,b,c和d,使得满足a+b+c+d = target. 找到所有的不重复解.

Solution

Analysis

K-Sum问题. 排序+夹逼.

排序
夹逼: K-2次循环, 内层进行左右夹逼.

此外,还要处理重复解问题, 和之前3Sum问题类似,跳过重复解.

Code

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

[LeetCode]18. 4Sum

Problem

Solution

Analysis

Code

推荐文章（由hexo文章推荐插件驱动）