###### tags: `LeetCode` `Two Pointer`

# 0015. 3Sum (Medium)
耗時：46 分鐘 (一開始的思路錯誤，看Hint導正)

## 題目
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

## 思路
1. 鎖定一個位置`i`，接下來以2Sum的方式解題，用set紀錄重複的組合(存成string)

* Time Complexity：O(n^2)
* Space Complexity：O(n^3)，在worst case下，set會記錄Cn取3的內容

### 程式碼

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        set<string> duplicates;
        int i = 0, j = nums.size() - 1;
        
        if (nums.size() < 3) { return ans; }
        
        sort(nums.begin(), nums.end());
        
        while (i < j) {
            int mid = i+1;
            
            while (mid < j) {
                int two_sum = nums[mid] + nums[j];
                
                if (two_sum + nums[i] == 0) {
                    string ans_str = to_string(nums[i]) +
                        to_string(nums[mid]) + to_string(nums[j]);
                    if (!duplicates.count(ans_str)) {
                        duplicates.insert(ans_str);
                        ans.push_back({nums[i], nums[mid], nums[j]});
                    }
                    ++mid;
                    --j;
                }
                else if (two_sum + nums[i] < 0) { ++mid; }
                else { --j; }
            }
            
            ++i;
            j = nums.size() - 1;
        }
        return ans;
    }
};