15. 3Sum

這是三數之和的問題。

這題要求在一個給定的整數陣列nums中，找出所有互不重複的三個元素組合[nums[i], nums[j], nums[k]]，使得它們的何為0，即：nums[i] + nums[j] + nums[k] = 0，同時必須滿足三個元素的索引i、j、k彼此不同。
這題的關鍵有兩點：
1.和為0（Sum to Zero）：三個數的和必需等於0。
2.不含重複組合（No Duplicate Triplets）：最終的解集不能包含重複的三元組。例如，[-1, 0, 1]和[0, 1, -1]視為同一個組合，只能出現一次。

這題的解題思路是結合排序（Sorting）和雙指針（Two Pointers），來高效地解決並避免重複。
以下是核心步驟：
1.排序：首先對整個陣列nums進行排序。排序後，可以更方便地處理重複元素並使用雙指針技術。

2.遍歷（Iterate）和固定第一個數：從頭開始遍歷陣列。在每一次迭代中，將當前元素nums[i]視為三元組中的第一個數（a）。此時，問題就變成了在nums[i]之後的子陣列中，找到另外兩個數nums[j]（b）和nums[k]（c），使得b + c = -nums[i]。這就是兩數之和（Two Sum）問題。

3.雙指針（Two Pointers）尋找後兩個數：對於固定的第一個數nums[i]，設置兩個指針：左指針（L）：指向i + 1的位置和右指針（R）：指向陣列的末尾（nums.length - 1）。設置完後，讓它們在L < R的條件下循環以下步驟：計算三個數的和S = nums[i] + nums[L] + nums[R]。如果S < 0：表示和太小了，需要增大和。因為陣列已排序，所以移動左指針L++，嘗試更大的nums[L]；如果S > 0：表示和太大了，需要減小和。所以移動右指針R--，嘗試更小的nums[R]；如果S = 0：找到一個有效的三元組，將$\text{[nums[i], nums[L], nums[R]]}$加入結果集。接著，需要移動L和R指針並跳過重複的元素，以尋找下一組可能的解。

至於要如何避免重複，要確保以下三個層次上不能出現重複：
1.第一個數nums[i]的重複：在遍歷i時，如果nums[i]和前一個數nums[i - 1]相同，則跳過當前的i，因為以nums[i - 1]開頭的所有有效組合已經被找到了。
2.第二個數nums[L]的重複：在找到一個有效解（S = 0）後，移動左指針L時，如果nums[L]和nums[L + 1]相同，應該一直移動L，直到它指向一個不同的數。
3.第三個數nums[R]的重複：同理，在找到一個有效解（S = 0）後，移動右指針Ｒ時，如果nums[R]和[R - 1}相同，應該要一直移動R，直到它指向一個不同的數。

除了上述的步驟，這題還有邊界和優化（Boundaries and Optimization）要處理：

1.長度檢查：如果陣列長度小於3，直接返回空列表。
2.提前終止：如果nums[i] > 0，則可以提前結束整個遍歷。因為陣列已排序，之後的所有數都大於0，三個正數相加不可能等於0。

時間複雜度分析（Time Complexity Analysis）：
排序：O(nlogn）。
外層循環：O(n)。
內層雙指針循環 (L 和 R)： 在外層循環的每一次迭代中，雙指針只會從兩端向中間移動一次，總共花費 O(n) 的時間。

總體時間複雜度： O(nlogn)+O(n⋅n)=O(n )。這比暴力解法的 O(n ) 有了顯著的優化。