> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/238.-product-of-array-except-self-m.md).

# 238. Product of Array Except Self (M)

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.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `2 <= nums.length <= 105`
* `-30 <= nums[i] <= 30`
* The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer.

**Follow up:** Can you solve the problem in `O(1)` extra space complexity? (The output array **does not** count as extra space for space complexity analysis.)

### Solution:

<https://www.jiuzhang.com/problem/product-of-array-except-self/>\
**Version 1:**

如果暴力计算每个位置的答案值的话，时间会达到`O(N^2)`。

如果先将所有数乘起来，每个位置除以当前的数，有可能会整型溢出。

观察可以发现，每个数其实就是它前面部分的积乘以后面部分的积。所有前缀的积，通过一次遍历即可算出来，后缀也是一样。我们可以边乘边算前缀积，同时将他乘在结果数组上，这样达到了`O(1)`的额外空间，同时不用到除法。

#### 代码思路

1. 令`result`为一个全是`1`的数组。
2. 令前缀积`prefixProduct`等于`1`，后缀积`postfixProduct`等于`1`。
3. 正序遍历数组`nums`，第`i`个位置先将结果乘上`prefixProduct`，再将`prefixProduct`乘上`nums[i]`。
4. 逆序遍历数组`nums`，第`i`个位置先将结果乘上`postfixProduct`，再将`postfixProduct`乘上`nums[i]`。
5. 返回`result`。

#### 复杂度分析

设数组长度为`N`。

**时间复杂度**

* 遍历两次数组，时间复杂度为`O(N)`。

**空间复杂度**

* 只需额外`O(1)`的时间，记录前缀积和后缀积。

```
public class Solution {
    /**
     * @param nums: an array of integers
     * @return: the product of all the elements of nums except nums[i].
     */
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int prefixProduct = 1, postfixProduct = 1;
        
        for (int i = 0; i < result.length; i++) {
            result[i] = 1;
        }
        
        // 将第 i 个位置乘上前 i - 1 个数的积
        for (int i = 0; i < result.length; i++) {
            result[i] *= prefixProduct;
            prefixProduct *= nums[i];
        }
        
        // 将第 i 个位置乘上后面数的积
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] *= postfixProduct;
            postfixProduct *= nums[i];
        }
        
        return result;
    }
}
```

**Version 2:**

Version 1 的空间复杂版。prefixProduct postfixProduct都用数组来装。

```
class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        int n = nums.length;
        
        int[] prefixProduct = new int[n];
        prefixProduct[0] = nums[0];
        for(int i = 1; i< n; i++ )
        {
            prefixProduct[i] = prefixProduct[i-1] * nums[i];
        }
        
        int[] postfixProduct = new int[n];
        postfixProduct[n-1] = nums[n-1];
        for(int i = n-2; i >= 0; i-- )
        {
            postfixProduct[i] = postfixProduct[i+1] * nums[i];
        }
        
        int[] result = new int[n];
        result[0] = postfixProduct[1];
        result[n-1] = prefixProduct[n-2];
        for(int i = 1; i< n-1; i++)
        {
            result[i] = prefixProduct[i-1] * postfixProduct[i+1];
        }
        
        return result;
        
    }
}
```