Product of Array Expect Self

# 問題

整数配列numsがが与えられる．そこで，$i$番目の要素がnumsの$i$番目以外の要素の積からなる配列answerを返す関数を書け．

# 答え

answer[i]を定義どおりに計算すると全体で$O(n^2)$．これを回避したい．answer[i]とanswer[i+1]のそれぞれの因数は共通している部分が多いので，無駄な計算をしていそう．そこで累積積（累積和からの造語）を考えてみるとうまくいきそう．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        p = 1
        n = len(nums)
        output = []
        for i in range(n):
            output.append(p)
            p = p * nums[i]
        p = 1
        for i in range(n-1, -1, -1):
            output[i] = output[i] * p
            p = p * nums[i]
        return output