# 15. 3Sum
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/3sum/
## MyCode!

## 解題思路
* 延伸 2 Sum 的 Two pointer 想法，此題時間複雜度應用後時間複雜度應為O(n**2)
* 3 Sum 多了一變數須相加，使用 for i ....迴圈創造後搭配 Two pointer 理論上可使程式執行
* 題目給個 list 沒排序，為方便運算，使用sort()由小到大排序
* 當 i 固定時，會設置一頭一尾進行 Two pointer index 去尋找總和為 0 的 value
1. 如果 **Sum = 0**，index = i,head,tail
2. 如果 **Sum > 0**，則代表 nums[head] + nums [tail] 太大，需要變小 ➡️ 往前移動 tail ( list 尾到頭，大到小，往前移，nums[head] + nums [tail] 值變小)
3. 如果 **Sum < 0** ，則代表 nums[head] + nums [tail] 太小，需要變大 ➡️ 往後移動 head ( list 頭到尾，小到大，往後移，nums[head] + nums [tail] 值變大)
4. **head 方向, tail 方向 = 往後, 往前**（我不考慮前前後後，太混亂😵‍💫）
* 要注意，可能答案會重複，所以要剔除重複的答案
* 輸出是一個二維 list ，最好先創一個空 list 把 ans append 進去，最後就 return list 🎉
## 解法
### Step 1:先創造 ans list（Global），然後把亂七八糟的原陣列 sort（）由小到大排序一下
### Step 2：寫一個 for i...，搭配一個 Two pointer 的 while 迴圈
* **for loop**( i 會作為一個原始頭，一個一個 i 會檢視他可以搭配的組合們)

* 我會再 for loop 與 while 之間創造一個 head = i+1（排除 i 的下一個作為起始，必點 i 與 head 重複），還會再創造一個 tail = len(nums)-1
* 上面說到的這個 head,tail 是一個 nonlocal ， 是 while 的global ***（我就是想創造對 while 是全域，對 for 是 local 的變數)***
1. 這樣 while 裡做的事可以直接改到他的全域，不斷去尋找下一個可能
2. 對 for 而言每次的 head,tail 都可以好好的 initial 👍

* **while** 條件：tail > head ***（固定方向，避免tail 被扣到超過頭。head 被加到超過尾，這樣會重複執行...跑不完）***
* **Sum == 0**：[nums[i],nums[head],nums[tail]]
1. 如果 ans list 裡面有這一組解答，表示如果再往前移動 tail 不是重複解答，就是 Sum < 0，直接換下一個 head 跑下一圈
2. 如果 ans list 裡面沒這一組解答，把解答 append 進 ans list 。如果再往前移動 tail 不是重複解答，就是 Sum < 0，直接換下一個 head 跑下一圈
* **Sum > 0**：則代表 nums[head] + nums [tail] 太大，需要變小 ➡️ 往前移動 tail
1. tail -= 1
* **Sum < 0**：則代表 nums[head] + nums [tail] 太小，需要變大 ➡️ 往後移動 head
1. head += 1