# 15 - 3Sum

解法一 - 先指定第一個 element，剩下的問題就是 2 Sum

我們可以先用一個 for 迴圈跑過所有的 first element，然後就用兩個 pointer - front & back 指向另外的兩個 element，這樣就可以讓原本暴力搜尋得花 O(N^3) 的時間複雜度下降到 O(N^2)。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        if(nums.size() < 3) return res;

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

        for(int i=0; i<nums.size(); i++) {
            int target = -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: 92 ms, faster than 96.61% of C++ online submissions for 3Sum. Memory Usage: 14.5 MB, less than 91.66% of C++ online submissions for 3Sum.