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]
]

AC代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4) return {};
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret(0);
        set<vector<int>> ans;
        for (int mid1 = 1; mid1 < nums.size() - 2; ++mid1) {
            for (int mid2 = mid1 + 1; mid2 < nums.size() - 1; ++mid2) {
                int left = 0, right = nums.size() - 1;
                while (left < mid1 && mid2 < right) {
                    int sum = nums[left] + nums[mid1] + nums[mid2] + nums[right];
                    if (sum == target) {
                        vector<int> tmp{nums[left], nums[mid1], nums[mid2], nums[right]};
                        ans.insert(tmp);
                        while (right > mid2 && nums[right] == nums[right - 1]) right--;
                        while (left < mid1 && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                    else if (sum < target) left++;
                    else if (sum > target) right--;
                }
            }
        }
        for (auto it = ans.begin(); it != ans.end(); ++it) {
            vector<int> tmp{(*it)[0], (*it)[1], (*it)[2], (*it)[3]};
            ret.push_back(tmp);
        }
        return ret;
    }
};

总结

3Sum的强化版，思路基本一样，多加判断条件及时退出循环可以使程序运行快三四倍