Description

Submission

The solution is bounded to be O(N^3), so we only need to iterate through the 2 outer loops and then solving the 2Sum problem in O(N).

[0],0 and [0,0,0,0],0 are 2 special cases.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if(nums.size() < 4) return res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); ++i) {
            for(int j = i + 1; j < nums.size(); ++j) {
                int tgt = target - nums[i] - nums[j];
                for(int x = j + 1, y = nums.size() - 1; x < y; ) {
                    int total = nums[x] + nums[y];
                    if(total < tgt) x++;
                    if(total > tgt) y--;
                    if(total == tgt) {
                        res.push_back({nums[i], nums[j], nums[x], nums[y]});
                        while(x < y && nums[x] == nums[x + 1]) x++;
                        x++;
                        while(x < y && nums[y] == nums[y - 1]) y--;
                        y--;
                    }
                }
                while(j + 1 < nums.size() && nums[j] == nums[j+1]) j++;
            }
            while(i + 1 < nums.size() && nums[i] == nums[i+1]) i++;
        }
        return res;
    }
};