前綴連乘: 除了自己之外的連乘積 Product of Array Except Self_Leetcode 精選75題

Enric Moreu on Unsplash

題目敘述

題目會給定我們一個輸入陣列nums，要求我們掃描每個陣列元素nums[i]，計算除了nums[i]以外的陣列元素連乘積。

題目的原文敘述

測試範例

Example 1:

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

nums[0] 以外的陣列元素連乘積 = 2 * 3 * 4 = 24
nums[1] 以外​的陣列元素連乘積 = 1 * 3 * 4 = 12
nums[2] 以外​的陣列元素連乘積 = 1 * 2 * 4 = 8
nums[3] 以外​的陣列元素連乘積 = 1 * 2 * 3 = 6

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

nums[0] 以外的陣列元素連乘積 = 1 * 0 * -3 * 3 = 0
nums[1] 以外​的陣列元素連乘積 = -1 * 0 * -3 * 3 = 0
nums[2] 以外​的陣列元素連乘積 = -1 * 1 * -3 * 3 = 9
nums[3] 以外​的陣列元素連乘積 = -1 * 1 * 0 * 3 = 0
nums[4] 以外​的陣列元素連乘積 = -1 * 1 * 0 * -3 = 0

約束條件

Constraints:

• 2 <= nums.length <= 10^5

輸入陣列長度介於2~10^5之間

• -30 <= nums[i] <= 30

陣列元素都介於-30 ~ 30 之間

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

保證連乘積不會超過 32bit整數的範圍

演算法

這題可以借用經典的前綴和prefix sum的觀念。

前綴和原本的定義是連續陣列元素的總和。

這邊，我們題目所要求的是扣除自己之外的連乘積，因此，我們可以寫成

對於nums[i]而言，扣除自己之外的連乘積

= nums[0] * num[1] * ... * nums[i-1] * nums[i+1] * nums[i+2] * ... nums[n-1]

= (nums[0] * num[1] * ... * nums[i-1]) * (nums[i+1] * nums[i+2] * ... nums[n-1])

= prefix product of (i-1) * postfix product of (i+1)

= 到(i-1)為止的前綴乘積 * 從(i+1)開始的後綴乘積

把上述的關係式，透過迴圈去做一個線性掃描，依序更新每個索引i所對應到的連乘積即可。