https://leetcode.com/problems/product-of-array-except-self/
## タグ
## 概要
> Given an integer array `nums`, return _an array_ `answer` such that_ `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`.
>
> The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer.
>
> You must write an algorithm that runs in `O(n)` time and without using the division operation.
## 方針
### Intuition
それぞれのindexに対して左側と右側の積を求めておけば、自身を除く積は左側と右側の積になる。
### Brute Force
Time Complexity: $O(n^2)$
単純に毎回自分以外の要素を掛ける。課題要件で$O(n)$が指定されているので使えない。
### すべての積を求めて自身の値で割る
課題要件として禁止されている。0が存在するとうまくいかない。
### 左側と右側の積を求める
Time Complexity: $O(n)$
Space Complexity: $O(n)$
Where: `n = len(nums)`
```python
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(n):
if i != n - 1:
left[i + 1] = left[i] * nums[i]
right[n - i - 2] = right[n - i - 1] * nums[n - i - 1]
ans = [0] * n
for i in range(n):
ans[i] = left[i] * right[i]
return ans
```
### 左側と右側の積を求める（改良版）
Time Complexity: $O(n)$
Space Complexity: $O(1)$
Where: `n = len(nums)`
左側の積と右側の積をそれぞれ配列で持たせるのではなく、ansの配列だけでやる。
```python
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
left = 1
right = 1
for i in range(n):
ans[i] *= left
ans[n - i - 1] *= right
left *= nums[i]
right *= nums[n - i - 1]
return ans
```
```python
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
prefix_left_product = 1
for i in range(n):
ans[i] *= prefix_left_product
prefix_left_product *= nums[i]
prefix_right_product = 1
for i in range(n - 1, -1, -1):
ans[i] *= prefix_right_product
prefix_right_product *= nums[i]
return ans
```