> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/presum/product-of-array-except-self.md).

# 238. Product of Array Except Self

https\://leetcode.com/problems/product-of-array-except-self/description/

> Given an array `nums` of *n* integers where *n* > 1,  return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.
>
> **Example:**
>
> ```
> Input:  [1,2,3,4]
> Output: [24,12,8,6]
> ```
>
> **Constraint:** It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
>
> **Note:** Please solve it **without division** and in O(*n*).
>
> **Follow up:**\
> Could you solve it with constant space complexity? (The output array **does not** count as extra space for the purpose of space complexity analysis.)

## Thoughts

依次求出每个数左边的连积和右边的连积。

## Code

```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        N, r = len(nums), 1
        res = [1] * N
        for i in range(1, N):
            res[i] = res[i - 1] * nums[i - 1]
        for i in reversed(range(N)):
            res[i] *= r
            r *= nums[i]
        return res
    
```

```cpp
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        const auto N = nums.size();
        vector<int> res(N);
        res[0] = 1;
        for (int i = 1, p = 1; i < N; ++i) {
            p *= nums[i - 1];
            res[i] = p;
        }
        for (int i = N - 2, p = 1; i >= 0; --i) {
            p *= nums[i + 1];
            res[i] *= p;
        }
        return res;
    }
};


```

## Analysis

Errors:

1. 当右边到达0时, res\[0]原先的值是0, 应不用乘res\[0].

时间复杂度O(N), 无额外空间.