15. 3Sum

Medium

Description

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

核心思路：排序後固定一個數，對剩餘部分用 Two Sum II 的雙指針解法，關鍵在於跳過重複元素來避免重複三元組。

3Sum 可以拆解為：固定 nums[i]，在 i+1..n-1 中找兩數之和為 -nums[i]
先排序讓相同值聚在一起，方便去重
去重策略：外層迴圈遇到相同的 nums[i] 就跳過；內層雙指針找到解後也跳過重複值

Approaches#

1: Brute Force + HashSet 去重#

概念: 三層迴圈列舉所有三元組，用 Set 去重
時間複雜度: O(n^3) - 三層巢狀迴圈
空間複雜度: 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(n)，內層雙指針 O(n)
空間複雜度: 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
    }
}

去重邏輯是此題最容易出錯的部分。外層 i > 0 && nums[i] == nums[i-1] 跳過的是「相同起點」；內層找到解後跳過重複值，確保不會產生相同三元組。注意跳過後還要再各移一步（left++; right--）。

🔑 Takeaways#

Pattern: kSum 問題的通用模式：排序 + 固定 k-2 個數 + Two Pointers 解 Two Sum
關鍵技巧: 排序後去重的技巧——跳過相鄰相同元素；提前剪枝（nums[i] > 0 即可 break）大幅減少無效計算