# 18 - 4Sum

解法一 - 先指定第一個 element，剩下就是 3Sum

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;

        sort(nums.begin(), nums.end());

        for(int i=0; i<nums.size(); i++) {
            vector<vector<int>> three_sum_res = threeSum(nums, i+1, target-nums[i]);

            if(!three_sum_res.empty()) {
                for( auto element : three_sum_res) {
                    element.insert(element.begin(), nums[i]);
                    res.push_back(element);
                }
            }

            while(i+1<nums.size() && nums[i+1]==nums[i])
                i++;
        }

        return res;
    }

private:
    vector<vector<int>> threeSum(vector<int>& nums, int startIndex, int inputTarget){
        vector<vector<int>> res;

        for(int i=startIndex; i<nums.size(); i++) {
            int target = inputTarget-nums[i];
            int front = i+1;
            int back = nums.size()-1;

            while(front < back) {
                int sum = nums[front] + nums[back];

                if(sum < target) {
                    front++;
                }
                else if(sum > target) {
                    back--;
                }
                else{
                    res.push_back({nums[i], nums[front], nums[back]});

                    // remove duplicate of front
                    while(front < back && nums[front] == res[res.size()-1][1])
                    front++;
                    // remove duiplicate of back
                    while(front < back && nums[front] == res[res.size()-1][2])
                    back--;
                }
            }

            // Make sure we won't start next search with the same first element
            while(i+1<nums.size() && nums[i+1] == nums[i])
                i++;
        }

        return res;
    }
};

跑起來的效率並不算很高，結果如下：

Runtime: 28 ms, faster than 76.22% of C++ online submissions for 4Sum. Memory Usage: 9.4 MB, less than 41.12% of C++ online submissions for 4Sum.