15. 3Sum

解題思路

有兩個地方會造成 duplicate:

一、第一層 for loop 的數值相同

譬如 [-4, -1, -1, 0, 1, 2] ，會先看到 index = 1 的那個 -1 ，找出解 [-1, 0, 1]。接著來到 index = 2 的 -1，這時又找出同樣的 [-1, 0, 1] 這組解。

要避免這種情況，必須檢查是不是跟前面的數值相同。

二、找 second, third 時數值相同

譬如 [-2, 0, 0, 2, 2]，會找到同樣的兩組 [-2, 0, 2]。

要避免這種情況，在移動 left, right 時也要檢查。

程式碼

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for(int i=0; i<nums.size() - 2; i++)
        {
            if(i != 0 && nums[i] == nums[i-1])
                continue;

            int left = i+1, right = nums.size() - 1;
            while(left < right)
            {
                if(left > i+1 && right < nums.size() - 1 && nums[left] == nums[left - 1] && nums[right] == nums[right + 1])
                {
                    left += 1;
                    right -= 1;
                    continue;
                }
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0)
                {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    left += 1;
                    right -= 1;
                }
                else if(sum < 0)
                    left += 1;
                else
                    right -= 1;
            }
        }
        return ans;
    }
};