LC18 4 Sum

本题链接：4 Sum

本题标签：Array，Two Pointers，Hash Table

本题难度：

英文题目 中文题目

---

方案1：

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

时间复杂度：

空间复杂度：

---