# 【LeetCode】 238. Product of Array Except Self

## Description
> Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

> Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

> Note: Please solve it without division and in O(n).

> Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

> 給予有n個整數的陣列nums且n > 1，回傳一個陣列output且output[i]等於nums所有元素的乘積除了nums[i]。

> 制約：保證乘積一定在32位元的表示範圍之內。

> 注意：請不使用除法並且在O(n)的時間複雜度之下完成此題。

> 進階：
你可以在常數等級的空間複雜度完成這題嗎？（output陣列並不算在額外空間之中。）

## Example:

Example:

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

## Solution

* 如果沒有除法的限制，這題就很簡單：
* 先算出所有元素的乘積，然後跑一次for將元素除回去即可。
* 但這樣這題就不會是中等難度了XD
* 不使用除法的情況之下，我們可以先想想，不乘上自己的話，就是`自己前面的乘積` * `自己後面的乘積`。
* 因此我們就跑兩次for，分別得到前面和後面的乘積，最後再一個for相乘即可得到答案。
* 時間複雜度`O(3n) = O(n)`。

---

* 挑戰的部分怎麼做呢？其實很簡單，仔細觀察後就會發現，`back`和`front`其實只需要其中一個，另一個的運算可以直接跟原本的`nums`結合就好。
* 在下方範例中保留`back`。
* 詳細的部分就請直接看下方code自己trace了。

### Code

* 一般

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> front(nums.size(), 1), back(nums.size(), 1);
        for(int i = 1; i < nums.size(); i++)
            back[i] = back[i - 1] * nums[i - 1];
        for(int i = nums.size() - 2; i >= 0; i--)
            front[i] = front[i + 1] * nums[i + 1];
        for(int i = 0; i < nums.size(); i++)
            nums[i] = front[i] * back[i];
        return nums;
    }
};

* 挑戰

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> back(nums.size(), 1);
        for(int i = 1; i < nums.size(); i++)
            back[i] = back[i - 1] * nums[i - 1];
        int temp = 1;
        nums.push_back(1);
        for(int i = back.size() - 1; i >= 0; i--)
        {
            temp *= nums[i + 1];
            back[i] *= temp;
        }
        return back;
    }
};

###### tags: `LeetCode` `C++`