# 【LeetCode】 15. 3Sum

## Description
> Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

> **Note**:
> The solution set must not contain duplicate triplets.

> 給一包含n個整數的陣列nums，有任意三個元素a, b, c能夠使a + b + c = 0 成立嗎？找到所有陣列中的三個數，相加總和為零。
> 提示：答案中不可有重複的組合。

## Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

## Solution

* 請先看完[1. Two Sum](https://hackmd.io/s/ryMr477o4)。
* 這題變為三個數字總和為零，那只要用loop將其中一個數字設為目標數跑過一輪即可。
* 為了加速，將數列先排列，然後根據總和太大或太小往中間慢慢靠近。
* 為了排除重複的組合，答案換為set再換回去(感覺有更好的做法，這樣做好像有點慢)。

### Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        vector<vector<int>> ans;
        
        if (nums.empty())
            return ans;
        
        sort(nums.begin(),nums.end());
        unordered_set<int> seen;
        
        int s = nums.size();
        for (int i = 0; i < s - 2; i++)
        {
            if (seen.find(nums[i]) != seen.end())
                continue;
            
            int target = -nums[i];
            int b = i + 1, e = s - 1;
            while (b < e)
            {
                if (nums[b] + nums[e] == target)
                {
                    ans.push_back({nums[b], nums[i], nums[e]});
                    b++;
                    e--;
                }
                else if (nums[b] + nums[e] > target)
                    e--;   
                else
                    b++;
            }
            seen.insert(nums[i]);
        }
        set<vector<int>> u(ans.begin(),ans.end());
        ans.assign(u.begin(),u.end());
        return ans;
    }
};

###### tags: `LeetCode` `C++`