給定整數陣列
nums和目標值target，找出所有不重複的四元組[nums[a], nums[b], nums[c], nums[d]]，使得a + b + c + d == target。
Example:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Intuition
TIP
核心思路：排序後，外層兩層迴圈固定前兩個數，內層用 Two Pointers 找剩下兩個數。本質是 3Sum 再包一層。
- 與 LC 15 (3Sum) 同樣的策略，只是多一層迴圈
- 排序後跳過重複元素避免重複結果
- 可以用提前剪枝加速
Approaches
1. Sort + HashSet Brute Force — O(n³) / O(n)
- Idea: 三層迴圈 + HashSet 找第四個數，用 Set 去重結果
- Time:
O(n³) - Space:
O(n)- HashSet
HashSet Code
class Solution {
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
nums.sort()
val result = mutableSetOf<List<Int>>()
for (i in 0 until nums.size - 3) {
for (j in i + 1 until nums.size - 2) {
val seen = mutableSetOf<Long>()
for (k in j + 1 until nums.size) {
val need = target.toLong() - nums[i] - nums[j] - nums[k]
if (need in seen) {
result.add(listOf(nums[i], nums[j], need.toInt(), nums[k]))
}
seen.add(nums[k].toLong())
}
}
}
return result.toList()
}
}⭐ 2. Sort + Two Pointers — O(n³) / O(1)
- Idea: 兩層外迴圈固定 i, j，內層 Two Pointers 找 left, right，每層跳過重複
- Time:
O(n³)- 兩層迴圈 * Two Pointers - Space:
O(1)- 不計結果空間
class Solution {
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
nums.sort()
val result = mutableListOf<List<Int>>()
val n = nums.size
for (i in 0 until n - 3) {
if (i > 0 && nums[i] == nums[i - 1]) continue
for (j in i + 1 until n - 2) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue
var left = j + 1
var right = n - 1
while (left < right) {
val sum = nums[i].toLong() + nums[j] + nums[left] + nums[right]
when {
sum == target.toLong() -> {
result.add(listOf(nums[i], nums[j], nums[left], nums[right]))
left++
right--
while (left < right && nums[left] == nums[left - 1]) left++
while (left < right && nums[right] == nums[right + 1]) right--
}
sum < target.toLong() -> left++
else -> right--
}
}
}
}
return result
}
}WARNING
必須使用 Long 來計算 sum，避免整數溢位（例如 nums = [1000000000, 1000000000, 1000000000, 1000000000]）。
🔑 Takeaways
- Pattern: kSum 通用框架 = (k-2) 層迴圈 + Two Pointers
- Key trick: 每一層都要跳過重複元素防止重複結果；注意 Long 溢位問題；可加入提前剪枝（當前最小值已大於 target 時 break）