# 238. Product of Array Except Self

### Leetcode

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

### 題目

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3,4]
</strong><strong>Output: [24,12,8,6]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [-1,1,0,-3,3]
</strong><strong>Output: [0,0,9,0,0]
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

如果可以用除法的話，屬於 easy 題，解法是直接遍歷矩陣兩次，需要注意的是

1. 如果原本矩陣中元素 = 0 的大於 2 個的話，全部回傳值都會是 0
2. 如果原本矩陣中元素 = 0 的等於 1 個的話，除了等於 0 的那個元素其他的回傳值都是 0

```javascript
var productExceptSelf = function(nums) {
    let total = 1;
    let zeroCount = 0;
    const result = [];

    for(let i=0; i<nums.length; i++) {
        if (nums[i] !== 0) {
            total *= nums[i];
            result[i] = i;
        } else {
            // 用 '0' 代表這個元素是 0
            result[i] = '0';
            zeroCount++;
        }
    }

    // 如果 0 大於兩個的話，回傳的所有元素都會是 0
    if (zeroCount > 1) {
        return result.map(r => 0);
    }

    for(let i=0; i<nums.length; i++) {
        if (result[i] === '0') {
            result[i] = total;
        } else {
            if (zeroCount > 0) {
                // 0 有一個，所以怎麼乘都是 0
                result[i] = 0;
            } else {
                result[i] = total / nums[i];
            }
        }
    }

    return result;
};
```

Runtime: 97 ms Beats 32.09% of users with JavaScript

Memory: 59.97 MB Beats 48.63% of users with JavaScript

* **方法二**

題目規定不能使用除法，那麼要怎麼才能求出除了自己之外乘起來的結果呢？

有一個特殊的思考方向是 **某個元素要求的答案 = 左邊所有元素的乘積 \* 右邊所有元素的乘積**

所以方法就是

1. 從左往右遍歷一次求得 **左邊所有元素的乘積**
2. 從右往左遍歷一次求得 **右邊所有元素的乘積**
3. 最後將元素左邊的乘積 \* 右邊的乘積即為答案

```javascript
var productExceptSelf = function (nums) {
    const l2r = [];
    const r2l = [];
    const result = [];
    let total = 1;

    for (let i = 0; i < nums.length; i++) {
        total *= nums[i];
        l2r[i] = total;
    }

    total = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        total *= nums[i];
        r2l[i] = total;

        if (i === 0) {
            result[i] = r2l[i + 1]
        } else if (i === nums.length - 1) {
            result[i] = l2r[i - 1]
        } else {
            result[i] = l2r[i - 1] * r2l[i + 1];
        }
    }

    return result;
};
```

**範例**：`[1, 2, 3, 4]`

`l2r = [1, 2, 6, 24]`

`r2l = [24, 24, 12, 4]`

所以以第二個元素 `2` 來看，結果就會是 `l2r[0] * r2l[2] = 1 * 12 = 12`

Runtime: 98 ms Beats 29.31% of users with JavaScript

Memory: 66.08 MB Beats 5.14% of users with JavaScript

* **方法三**

方法二中的 l2r 是由左往右遍歷，r2l 是由右往左遍歷，不會互相影響，所以我們可以用同一個 result 矩陣來儲存方法二中的 l2r 及 r2r 的結果，以達到空間上的優化

```javascript
var productExceptSelf = function (nums) {
    const result = [];
    let total = 1;

    for (let i = 0; i < nums.length; i++) {
        // 因為 result[i] 是前面所有元素的乘積，所以這裡先賦值 result[i]
        result[i] = total;
        total *= nums[i];
    }

    total = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] *= total;
        total *= nums[i];
    }

    return result;
};
```

Runtime: 80 ms Beats 85.04% of users with JavaScript

Memory: 61.21 MB Beats 30.36% of users with JavaScript

### 參考資料

{% embed url="<https://weikaiwei.com/algorithm/leetcode-238/>" %}

{% embed url="<https://www.cnblogs.com/grandyang/p/4650187.html>" %}
