# 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;
        
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/6.array/238.-product-of-array-except-self-m.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.