# 15 - 3Sum

解法一 - Two Pointer

這題開始延伸到要找 triplets，而且一開始 array 是沒有排序的。如果仔細觀察題目，會發現要求的輸出不像 Two Sum 是 index，而是實際的值。所以即便我們先 sort 過 array 也沒有關係。

到這邊基本的想法就出來了，既然可以 sort array，那尋找 nums[i]+nums[j] == target 就可以用 two pointer。既然尋找 nums[i]+nums[j] == target 已經有了有效率的演算法，那我們就依序把每一個 element 當作 triplet 裡的第一個 element，然後把 nums[i] 跟 nums[j] 當作第二個和第三個 element。就可以實作出下面的程式碼：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> triplets;
        int n = nums.size();

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

        // Note:
        // 1. Iterate to n-2 only
        // 2. Need to skip same element to avoid duplicate triplets
        for(int i=0; i<n-2; i++) {
            // skip same element to avoid duplicate triplets
            if (i > 0 && nums[i] == nums[i - 1]) {  
                continue;
            }
            searchPair(nums, -nums[i], i+1, triplets);
        }

        return triplets;    
    }

private:
    void searchPair(vector<int>& nums, int target, int start, vector<vector<int>>& triplets) {
        int l=start, r=nums.size()-1;

        while(l<r) {
            if(nums[l]+nums[r] == target) {
                triplets.push_back({-target, nums[l], nums[r]});

                // Intuitively, we should only do l++ or r--
                // so that we won't miss the case of nums[l]+nums[r-1] or nums[l+1]+nums[r]
                // But think deeper, if we only do r--
                // After preventing duplicates, we know that
                // nums[l] and nums[new r] cannot fulfill sum==target
                // So we won't miss anything even we do l++ and r--
                l++;
                r--;

                while (l < r && nums[l] == nums[l-1]) {
                    l++;  // skip same element to avoid duplicate triplets
                }
                while (l < r && nums[r] == nums[r+1]) {
                    r--;  // skip same element to avoid duplicate triplets
                }
            }
            else if(nums[l]+nums[r] > target) r--;
            else if(nums[l]+nums[r] < target) l++;
        }
    }
};