NeetCode 150 [Arrays & Hashing]:medium 4/6

NeetCodeのSolutionを書いていく

Products of Array Except Self

問題概要

整数の配列numsが与えられます。
整数の配列を返します。その整数はnums[i]以外の数字の累積です。
それぞれの積は32bitを超えないことが保証されます。

割り算を使わずにO(n)で解けますか？

配列数は2以上1000以下
整数は-20以上20以下

計算時間はO(n)、メモリーはO(n)を目指す。

例

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

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

メモ

問題を読みながら、全て掛け合わせておいて、自分自身で割った数を出そうと思っていたら。。。
問題の最後に「割り算を使わずに出来るか？」という記載が！
割り算を使わずにO(n)で処理を完了するには・・・？

わからんから答え見ちゃった。
前からの掛け算の結果(prefix)と、後ろからの掛け算(suffix)の結果をi番目の配列に保存しておいて、
配列i番目の結果はprefix[i-1] x suffix[i+1]で計算できる！
更にメモリ使用量をO(1)にできる解法も紹介されている。
とりあえずシンプルな方で実装してみた。

インデックスの指定がむずい！
理解できん・・・テストが通るまで色々試すという。知能不足🧠

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)
        prefix = [1] * len(nums)
        suffix = [1] * len(nums)
        num = len(nums)

        for i in range(1, num, 1):
            prefix[i] = prefix[i - 1] * nums[i - 1]

        for i in range(num - 2, -1, -1):
            suffix[i] = suffix[i + 1] * nums[i + 1]

        for i in range(num):
            res[i] = prefix[i] * suffix[i]

        return res