---
# System prepended metadata

title: leetcode 238 Product of Array Except Self
tags: [leetcode, Javascript]

---

# leetcode 238 Product of Array Except Self
###### tags: `leetcode` `Javascript`

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const result = [];
    let productSoFar = 1;
    for (let i = 0; i < nums.length; i++) {
        result[i] = productSoFar;
        productSoFar *= nums[i]
    }
    
    productSoFar = 1;
    for (let j = nums.length - 1; j >= 0; j--) {
        result[j] *= productSoFar;
        productSoFar *= nums[j];
    }
    return result;
};
```

## 解析
不能用除法，代表一開始不能乘進去，於是我們可以拆成兩部分

```
input [1,2,3,4,5] 

result 1 = product []        * product [2,3,4,5]
result 2 = product [1]       * product [3,4,5]
result 3 = product [1,2]     * product [4,5]
result 4 = product [1,2,3]   * product [5]
result 5 = product [1,2,3,4] * product []
```

當前 index 的結果為前面相乘的結果乘以後半部相乘的結果。

預先乘好不包含自己的前半部及後半部

```javascript
let product = 1;
// 前半部
const productFronts = [];
for(let i = 0; i < nums.length; i++){
    productFronts.push(product);
    product *= nums[i];
}

// 後半部
product = 1;
const productBacks = [];
for(let i = nums.length - 1; i >= 0; i--){
    productFronts.unshift(product);
    product *= nums[i];
}

```

結果為

```
                ->
productFronts = [1, 1, 2, 6, 24]
                                <-
productBacks = [120, 60, 20, 5, 1]
```

`productFronts` 與 `productBacks` 相乘及為答案

```
[  1,   1,   2,  6, 24]
   x    x    x   x   x
[120,  60,  20,  5,  1]

[120,  60,  60, 30, 24] 
```

## 再化簡
後半部的部分可以不必重新紀錄，可以在從最後面累乘的時候順便與前半部相乘直接為當前 index 答案。