# [LeetCode 75] DAY 7 - Product of Array Except Self

## 題目：
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.

## 解題思考

### 第一次嘗試
- 要有一個存放新數字的陣列
- 每個位置都需要去乘上其他位置的數字(雙迴圈)
- 當兩個迴圈位置相同時(`i = j`) 跳過
- 這個方式會超時，時間複雜度是`O(n^2)` 空間複雜度為`O(n)`

### 第二次嘗試
- 為了降低時間，不能使用雙迴圈
- 用分開的兩個迴圈(前綴+後綴)
- 前綴：算出當前位置<u>以前</u>的所有數字乘積
- 後綴：算出當前位置<u>之後</u>的所有數字乘積

## 程式碼
1.

function productExceptSelf(nums) {
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        let curr = 1; // 確保初始值
        
        for (let j = 0; j < nums.length; j++) {
            if (j != i) {
                curr *= nums[j];
            }
        }
        result.push(curr);
    }

    return result;    
}

2.

function productExceptSelf(nums) {
    const result = [];

    let prefix = 1;
    for (let i = 0; i < nums.length; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }

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

    return result;
}

## 延伸思考
- Prefix Sum
- 時間複雜度與空間複雜度

## 相關資源
- [238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/description/)