238. Product of Array Except Self

Medium

Description

給定整數陣列 nums，回傳陣列 answer，其中 answer[i] 等於 nums 中除了 nums[i] 以外所有元素的乘積。不能使用除法，且必須在 O(n) 時間內完成。

Example:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Intuition#

核心思路：answer[i] = 左邊所有數的乘積 * 右邊所有數的乘積，用前綴積和後綴積拆解。

不能用除法，所以不能「全部乘起來再除以 nums[i]」
每個位置的答案可以拆成：左側前綴積 x 右側後綴積
可以先用一個陣列存前綴積，再反向掃一遍乘上後綴積，達到 O(1) 額外空間

Approaches#

1: Two Arrays (Prefix + Suffix)#

概念: 分別建立前綴積陣列和後綴積陣列，answer[i] = prefix[i] * suffix[i]
時間複雜度: O(n) - 三次線性遍歷
空間複雜度: O(n) - 額外的前綴和後綴陣列

class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        val n = nums.size
        val prefix = IntArray(n) { 1 }
        val suffix = IntArray(n) { 1 }

        for (i in 1 until n) {
            prefix[i] = prefix[i - 1] * nums[i - 1]
        }
        for (i in n - 2 downTo 0) {
            suffix[i] = suffix[i + 1] * nums[i + 1]
        }

        return IntArray(n) { prefix[it] * suffix[it] }
    }
}

⭐2: Single Array with Running Suffix#

概念: 先將前綴積直接存入結果陣列，再用一個變數從右往左累積後綴積，逐一乘入結果
時間複雜度: O(n) - 兩次線性遍歷
空間複雜度: O(1) - 除了輸出陣列外只用一個變數（題目聲明輸出陣列不計入空間）

class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        val n = nums.size
        val answer = IntArray(n)

        // 前綴積存入 answer
        answer[0] = 1
        for (i in 1 until n) {
            answer[i] = answer[i - 1] * nums[i - 1]
        }

        // 反向掃描，用 suffix 變數累積後綴積
        var suffix = 1
        for (i in n - 1 downTo 0) {
            answer[i] *= suffix
            suffix *= nums[i]
        }

        return answer
    }
}

題目明確說「output array does not count as extra space」，所以第二種解法的空間複雜度被視為 O(1)。面試時記得確認這個假設。

🔑 Takeaways#

Pattern: Prefix / Suffix 分解——將每個位置的答案拆成「左邊貢獻」和「右邊貢獻」
關鍵技巧: 先把一個方向的結果存入答案陣列，再用一個變數從反方向掃描累積，省去第二個陣列。此技巧可推廣到 Trapping Rain Water 等題目