18. 4Sum

Medium

Description

給定整數陣列 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#

核心思路：排序後，外層兩層迴圈固定前兩個數，內層用 Two Pointers 找剩下兩個數。本質是 3Sum 再包一層。

與 LC 15 (3Sum) 同樣的策略，只是多一層迴圈
排序後跳過重複元素避免重複結果
可以用提前剪枝加速

Approaches#

1: 排序 + HashSet 暴力#

概念: 三層迴圈 + HashSet 找第四個數，用 Set 去重結果
時間複雜度: O(n³)
空間複雜度: O(n) - HashSet

HashSet 程式碼

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: 排序 + Two Pointers#

概念: 兩層外迴圈固定 i, j，內層 Two Pointers 找 left, right，每層跳過重複
時間複雜度: O(n³) - 兩層迴圈 * Two Pointers
空間複雜度: 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
    }
}

必須使用 Long 來計算 sum，避免整數溢位（例如 nums = [1000000000, 1000000000, 1000000000, 1000000000]）。

🔑 Takeaways#

Pattern: kSum 通用框架 = (k-2) 層迴圈 + Two Pointers
關鍵技巧: 每一層都要跳過重複元素防止重複結果；注意 Long 溢位問題；可加入提前剪枝（當前最小值已大於 target 時 break）