# 238. Product of Array Except Self

[leetcode網址](https://leetcode.com/problems/product-of-array-except-self/description/)

## 問題
把診個陣列除了自己的數值算乘積，不能使用除法

Example 1:

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

## Idea
1. 算prefix product和suffix product
2. `prefix[i]`: 不包括`i`前的所有值的乘積

    prefix[i] = nums[0]*nums[1]*...*nums[i-1]

3. `suffix[i]`: 不包括`i`後的所有值的乘積

    suffix[i] = nums[n-1]*nums[n-2]*...*nums[i+1]

4. 最後答案就是

    ans[i] = prefix[i] * suffix[i]

## Solution
時間複雜度=O(N)；空間複雜度=O(N)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size(), product=1;
        vector<int>prefix(n, 1);
        for(int i=0; i<n; i++){
            prefix[i] = product;
            product*=nums[i];
        }

        vector<int>suffix(n, 1);
        product = 1;
        for(int i=n-1; i>=0; i--){
            suffix[i] = product;
            product*=nums[i];
        }

        for(int i=0; i<n; i++){
            prefix[i] *= suffix[i];
        }
        
        return prefix;
    }
};

## Follow up