# Leetcode --- 3Sum

## 15. 3Sum (Medium)
### 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.

Notice that the solution set must not contain duplicate triplets.

:::info
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. 將3Sum轉換成2Sum問題。
2. 將矩陣排序後，遍尋陣列，令==目標數字(0) 減去 當前元素==為目標值, 從剩餘陣列的**頭尾兩端**依序往內尋找兩數字相加為目標值，即可得到解。

選擇解法為2

### 解法細節
注意要避免重複記錄相同的解，有三個地方要注意，分別是頭、左、右元素。

### Python Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums)-2):
            l = i + 1
            r = len(nums) - 1
            target = -nums[i]
            if(i > 0 and nums[i] == nums[i-1]):
                continue
            while(l < r):
                if((nums[l] + nums[r]) == target):
                    res.append([nums[i], nums[l], nums[r]])
                    while(l<r and nums[l] == nums[l+1]):
                        l += 1
                    while(l<r and nums[r] == nums[r-1]):
                        r -= 1
                    l += 1
                    r -= 1
                elif((nums[l] + nums[r]) < target):
                    l += 1
                else:
                    r -= 1
        return res

---

if(i > 0 and nums[i] == nums[i-1]):

此行目的在於避免算入相同的解，若頭元素已出現過，則代表已將可能解加入進去。
i>0的用意是若給入全為0的陣列，少了這條件判斷會出錯。

---

while(l < r):
    if((nums[l] + nums[r]) == target):
        res.append([nums[i], nums[l], nums[r]])
        while(l<r and nums[l] == nums[l+1]):
            l += 1
        while(l<r and nums[r] == nums[r-1]):
            r -= 1
        l += 1
        r -= 1
    elif((nums[l] + nums[r]) < target):
        l += 1
    else:
        r -= 1

此段為本題精華，可以看到有許多條件判斷。
if、elif、else為判斷是否等於目標值的三種情況。
if內為若等於目標值的情況，兩個while分別為了避免左元素及右元素為相同導致記錄到重覆解。
排除掉重複解的可能性後，再將左右指標各往內縮。

不管是外圍的while還是內部while都需要加上l<r的判斷，
若l>r，除了會導致out of index，其後也不會有解出現。

###### tags: `leetcode` `array` `medium`