# LC 15. 3Sum

### [Problem link](https://leetcode.com/problems/3sum/)

###### tags: `leedcode` `medium` `python` `c++` `Two Pointer`

Given an integer array nums, return all the triplets <code>[nums[i], nums[j], nums[k]]</code> such that <code>i != j</code>, <code>i != k</code>, and <code>j != k</code>, and <code>nums[i] + nums[j] + nums[k] == 0</code>.

Notice that the solution set must not contain duplicate triplets.

**Example 1:**

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

**Example 2:**

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

**Example 3:**

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

**Constraints:**

- <code>3 <= nums.length <= 3000</code>
- <code>-10⁵ <= nums[i] <= 10⁵</code>

## Solution 1 - Two Pointer
#### Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        nums, res = sorted(nums), []
        
        for i in range(len(nums)-2):
            cur, left, right = nums[i], i + 1, len(nums) - 1
            if res != [] and res[-1][0] == cur:
                continue

            while left < right:
                if cur + nums[left] + nums[right] == 0:
                    res.append([cur, nums[left], nums[right]])
                    while left < right - 1 and nums[left] == nums[left + 1]:
                        left += 1
                    while left + 1 < right and nums[right] == nums[right - 1]:
                        right -= 1
                if cur + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1

        return res

#### C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res;
        
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) {
                    j++;
                } else if (sum > 0) {
                    k--;
                } else {
                    res.push_back({nums[i], nums[j], nums[k]});
                    j++;
                    while (j < k && nums[j - 1] == nums[j]) {
                        j++;
                    }
                    k--;
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return res;
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O(1) |

## Note
sol1:
大致思路如下圖: [ref](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.md)

代碼隨想錄的code寫複雜了, 應該可以更簡潔的.
`--------------------------------------------------------`

while (left < right - 1 and nums[left] == nums[left + 1]) {
    left++;
}
while (left < right - 1 and nums[right] == nums[right - 1]) {
    right--;
}
res.push_back({nums[cur], nums[left++], nums[right--]});

這裡不能寫成

res.push_back({nums[cur], nums[left++], nums[right--]});
while (left < right - 1 and nums[left] == nums[left + 1]) {
    left++;
}
while (left < right - 1 and nums[right] == nums[right - 1]) {
    right--;
}

因為要先找出左右重複的區塊再將結果加到res中, 不然會error, 是一個要注意的小地方

另外這次發現了一個新的寫法:

res.push_back({nums[cur], nums[left++], nums[right--]});
我通常習慣寫成
res.push_back(vector<int>{nums[cur], nums[left++], nums[right--]});

這是chatGPT的解釋:
挺酷的, 可以學起來.

c++:
[Ref(video)](https://www.bilibili.com/video/BV1bP411c7oJ/?spm_id_from=333.788&vd_source=088937f16fb413336c0cb260ed86a1c3)