題目描述:給定整數陣列 nums 和整數 target,找出所有不重複的四元組 [a, b, c, d],使得 a + b + c + d == target,回傳所有結果(順序不拘)。
解題思路:這是 3Sum 的延伸。先排序陣列,再用兩層外層迴圈固定前兩個數(指針 i 和 j),然後用雙指針 l = j+1、r = n-1 在剩餘部分夾逼尋找滿足條件的兩個數。每一層都必須做去重:i 層跳過與前一個相同的元素,j 層同理,找到合法四元組後 l 和 r 也需跳過重複值。此外可加入兩個剪枝:若當前四數最小和已大於 target,內層無需繼續;若當前四數最大和小於 target,直接跳到下一個 i。
時間複雜度:O(n³) — 排序 O(n log n),兩層外層迴圈 O(n²),每次雙指針掃描 O(n),合計 O(n³)。剪枝可大幅減少常數因子,但最差情況仍為 O(n³)。
空間複雜度:O(1) — 不計輸出陣列,只使用常數個指針與臨時變數(排序原地進行)。
1. Sort nums in ascending order.
2. For i from 0 to n-4:
a. Skip if nums[i] == nums[i-1] (duplicate).
b. Pruning: break if min possible 4-sum > target; continue if max possible 4-sum < target.
c. For j from i+1 to n-3:
- Skip if nums[j] == nums[j-1] (duplicate, and j > i+1).
- Apply similar pruning for j.
- Set l = j+1, r = n-1.
- While l < r:
* Compute sum = nums[i]+nums[j]+nums[l]+nums[r].
* If sum == target: record quadruplet, skip duplicates on both l and r, move both inward.
* If sum < target: l++.
* If sum > target: r--.
3. Return result.方法一:暴力四重迴圈(Brute Force) — 枚舉所有四元組,用 Set 去重,時間複雜度 O(n⁴),空間 O(n)。n 超過 100 即會超時,僅用於理解題意。
方法二:排序 + 雙指針(最優解) — 如本題解,時間 O(n³)、空間 O(1)(不含輸出)。加上剪枝後實際速度顯著快於純 O(n³)。
方法三:雜湊表輔助(Hash Map) — 預先將所有兩兩之和存入雜湊表(值 → pair 列表),再枚舉所有兩兩組合查詢補數,理論上可達 O(n²) 時間,但去重邏輯複雜且空間 O(n²),實作難度高,實際效能不一定優於雙指針。
long long 做加法,為什麼必要?在什麼情況下 int 會溢位?