給定整數陣列
nums，找出所有不重複的三元組[nums[i], nums[j], nums[k]]，使得i != j != k且nums[i] + nums[j] + nums[k] == 0。
Example:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Intuition
TIP
核心思路：排序後固定一個數，對剩餘部分用 Two Sum II 的雙指針解法，關鍵在於跳過重複元素來避免重複三元組。
- 3Sum 可以拆解為：固定
nums[i]，在i+1..n-1中找兩數之和為-nums[i] - 先排序讓相同值聚在一起，方便去重
- 去重策略：外層迴圈遇到相同的
nums[i]就跳過；內層雙指針找到解後也跳過重複值
Approaches
1. Brute Force + HashSet Dedup — O(n^3) / O(n)
- Idea: 三層迴圈列舉所有三元組，用 Set 去重
- Time:
O(n^3)- 三層巢狀迴圈 - Space:
O(n)- 儲存去重用的 Set
class Solution {
fun threeSum(nums: IntArray): List<List<Int>> {
val result = mutableSetOf<List<Int>>()
nums.sort()
for (i in 0 until nums.size - 2) {
for (j in i + 1 until nums.size - 1) {
for (k in j + 1 until nums.size) {
if (nums[i] + nums[j] + nums[k] == 0) {
result.add(listOf(nums[i], nums[j], nums[k]))
}
}
}
}
return result.toList()
}
}⭐ 2. Sort + Two Pointers — O(n^2) / O(1)
- Idea: 排序後，外層迴圈固定第一個數，內層用相向雙指針找另外兩個數，遇到重複值跳過
- Time:
O(n^2)- 外層 O(n)，內層雙指針 O(n) - Space:
O(1)- 忽略排序與輸出的空間（依實作，排序可能需 O(log n)）
class Solution {
fun threeSum(nums: IntArray): List<List<Int>> {
nums.sort()
val result = mutableListOf<List<Int>>()
for (i in 0 until nums.size - 2) {
// 排序後若第一個數 > 0，三數之和不可能為 0
if (nums[i] > 0) break
// 跳過重複的第一個數
if (i > 0 && nums[i] == nums[i - 1]) continue
var left = i + 1
var right = nums.size - 1
while (left < right) {
val sum = nums[i] + nums[left] + nums[right]
when {
sum < 0 -> left++
sum > 0 -> right--
else -> {
result.add(listOf(nums[i], nums[left], nums[right]))
// 跳過重複的第二、三個數
while (left < right && nums[left] == nums[left + 1]) left++
while (left < right && nums[right] == nums[right - 1]) right--
left++
right--
}
}
}
}
return result
}
}WARNING
去重邏輯是此題最容易出錯的部分。外層 i > 0 && nums[i] == nums[i-1] 跳過的是「相同起點」；內層找到解後跳過重複值，確保不會產生相同三元組。注意跳過後還要再各移一步（left++; right--）。
🔑 Takeaways
- Pattern: kSum 問題的通用模式：排序 + 固定 k-2 個數 + Two Pointers 解 Two Sum
- Key trick: 排序後去重的技巧——跳過相鄰相同元素；提前剪枝（
nums[i] > 0即可 break）大幅減少無效計算