18. 4Sum

這是一個關於在陣列中尋找四個數之和（4Sum）的問題。

這題給定一個包含 n 個整數的陣列 nums 和一個目標值 target，任務是找出所有唯一的四元組 [nums[a],nums[b],nums[c],nums[d]]，這些四元組必須滿足以下條件：

陣列中的四個元素的索引 a,b,c,d 都是不同的 (0≤a,b,c,d<n)。

這四個數的總和必須等於目標值：nums[a]+nums[b]+nums[c]+nums[d]==target。

這題的關鍵有以下兩點：
唯一性 (Uniqueness): 最終結果中不能包含重複的四元組。例如，如果 [1, 0, 0, -1] 是一個有效的四元組，那麼 [0, 1, -1, 0]（只是順序不同）或另一個由相同四個數組成的四元組，就不能再次被加入結果集。通常，為了確保唯一性，我們會對四元組內部的元素進行排序，例如將其表示為 [-1, 0, 0, 1]，然後只保留唯一的排序後結果。

效率 (Efficiency): 由於 n 的範圍是 1≤n≤200，一個簡單的四重迴圈（時間複雜度為 O(n^4)會太慢。我們需要一個更高效的方法，例如 O(n^3) 或更好。

解決這個問題最常見且高效的方法是將其降維：將 4Sum 問題轉化為多個 2Sum 問題。這種方法的時間複雜度為 O(n^3)

核心思路：排序 + 雙指針
排序 (Sorting): 首先，對輸入陣列 nums 進行排序。這是至關重要的一步，因為它有助於：

跳過重複元素： 確保我們不會處理重複的四元組。

使用雙指針： 排序後的陣列使得我們可以使用高效的雙指針 (Two Pointers) 技術來解決內部的 2Sum 問題。

固定前兩個數 (Two Fixed Pointers): 使用兩層巢狀迴圈，分別固定四元組中的第一個數 a 和第二個數 b。

外層迴圈遍歷 a，從索引 i=0 到 n−4。

內層迴圈遍歷 b，從索引 j=i+1 到 n−3。

雙指針解決 2Sum 問題 (Two Pointers for 2Sum): 對於固定的 nums[i] 和 nums[j]，我們的目標變成了在陣列剩餘的部分（從 j+1 到 n−1）中找到另外兩個數 nums[l] 和 nums[r]，使得：

nums[l]+nums[r]=新目標值

其中 新目標值=target−nums[i]−nums[j]。

設置左指針 l=j+1 和右指針 r=n−1。

在 l<r 的條件下迴圈：

計算當前四個數的和 sum=nums[i]+nums[j]+nums[l]+nums[r]。

如果 sum==target： 找到一個解！將 [nums[i],nums[j],nums[l],nums[r]] 加入結果集。然後，同時移動 l 和 r，並跳過任何重複的元素，以確保下一個找到的解是唯一的。

如果 sum<target： 總和太小，需要更大的數，移動左指針 l←l+1。

如果 sum>target： 總和太大，需要更小的數，移動右指針 r←r−1。

跳過重複元素 (Skipping Duplicates): 在三個地方需要檢查並跳過重複的元素：

在外層迴圈（固定 nums[i] 時）：如果 nums[i]==nums[i−1]，則跳過 i。

在內層迴圈（固定 nums[j] 時）：如果 nums[j]==nums[j−1]，則跳過 j。

在雙指針迴圈中找到解之後：移動 l 時，如果 nums[l]==nums[l−1]，則跳過 l；移動 r 時，如果 nums[r]==nums[r+1]，則跳過 r。

這題的注意事項有以下兩點：

溢出處理 (long): 由於題目中 nums[i] 和 target 的值範圍高達 10^9
，四個數的和可能達到 4×10^9，這會超出標準 32 位整數 (int) 的最大值 (≈2.1×10^9)。因此，在計算總和 currentSum 時，必須使用 long 類型來避免整數溢出錯誤。

時間複雜度: 排序是 O(nlogn)，三層巢狀迴圈（兩層遍歷固定數 i 和 j，一層雙指針 O(n)）總體是 O(n^3)。因此，總體時間複雜度為 O(n^3)，對於 n=200 的約束是可接受的。