題目描述:給定整數陣列 nums,找出所有不重複的三元組 [a, b, c] 使得 a + b + c = 0。
解題思路:先排序陣列,然後固定第一個數 nums[i],對剩餘部分用雙指標(left, right)尋找兩數之和等於 -nums[i]。排序後可以輕鬆跳過重複元素:固定 i 時跳過相同的 nums[i],找到答案後也跳過左右指標的重複值。時間複雜度 O(n²),是此類問題的最優解。
時間複雜度:O(n²) — 排序 O(n log n),外層迴圈 × 雙指標各 O(n)。
空間複雜度:O(1) 額外空間(排序若為原地)。
1. Sort nums
2. For i from 0 to n-3:
a. Skip if nums[i] == nums[i-1] (duplicate)
b. Set left = i+1, right = n-1
c. While left < right:
- sum = nums[i] + nums[left] + nums[right]
- If sum == 0: record triplet, skip duplicates, move both pointers
- If sum < 0: left++
- If sum > 0: right--
3. Return result雜湊集合尋找第三元素 O(n²):對每一對 (i, j),在集合中查詢 -(nums[i]+nums[j])。難以乾淨地去重。
無排序的雜湊方法:無序但需要複雜的去重邏輯(使用已排序三元組集合)— 平均仍 O(n²) 但常數較差。