---
tags: LeetCode,Top 100 Liked Questions
---
# 15. 3Sum
https://leetcode.com/problems/3sum/
## 題目敘述
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.
## Example
Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

## 解題想法
### 1.暴力破解(利用set)
利用set中元素不重複特性達成i != j, i != k, and j != k

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {    
        vector<vector<int>> res;
        
        set<vector<int>> hashSet;
        sort(nums.begin(), nums.end());
        if(nums.size()>=3){
             
            for(int i=0; i<nums.size()-2; i++)
                for(int j=i+1; j<nums.size()-1; j++)
                    for(int k=j+1; k<nums.size(); k++){
                        if(nums[i] + nums[j] + nums[k] == 0){
                                hashSet.insert({nums[i], nums[j], nums[k]});   
                        }
                }
        }
        
        res.assign(hashSet.begin(), hashSet.end());
        return res;
    }
};

時間複雜度為O(N^3)
會在315 test case TLE
### 2.
利用2個pointer紀錄排序後的left,right(頭尾)
並在紀錄後跳過重複項

vector<vector<int>> threeSum(vector<int> &nums)
{
    vector<vector<int>> ans;
    int n = nums.size();
    if (n < 3)
    {
        return {};
    }
    sort(nums.begin(), nums.end());
    for (int i = 0; i < n; i++)
    {
        int first = nums[i];
        int l = i + 1, r = n - 1;
        while (l < r)
        {
            int second = nums[l], third = nums[r];
            if ((first + second + third) == 0)
            {
                ans.push_back({first, second, third});
                while (l <= r && second == nums[l])
                {
                    l++;
                }
                while (l <= r && third == nums[r])
                {
                    r--;
                }
            }
            else if ((first + second + third) > 0)
            {
                r--;
            }
            else
            {
                l++;
            }
        }
        while (i < n-2 && nums[i] == nums[i + 1])
        {
            i++;
        }
    }
    return ans;
}

時間複雜度為O(N^2)