###### tags: `Leetcode` `medium` `array` `prefix sum` `python` `c++` `Top 100 Liked Questions`

# 238. Product of Array Except Self

## [題目連結:] 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.

**Follow up**: Can you solve the problem in ```O(1)``` extra space complexity? (The output array **does not** count as extra space for space complexity analysis.)

**Example 1:**

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

**Example 2:**

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

## 解題想法:
* 此題為求數組中各位置為: **除了自己以外的乘積**
* 不能用除法
* 要求O(n) time

* 使用prefix sum判斷:
* 從左到右，紀錄每個位置 **左邊成積和**
* 從右到左，紀錄每個位置 **右邊成積和**
* 各位置相乘整合即可

ex: nums = [ 1, 2, 3, 4]

    left = [ 1, 1, 2, 6]
    right= [24,12, 4, 1]
    
     res = [24,12, 8, 6]

## Python: Sol1
* time、space: O(n)

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #由左到右先求每個數的「左」邊乘積和
        res = [1]*len(nums)
        for i in range(1,len(nums)):
            res[i]=nums[i-1]*res[i-1]
        tmp = [1]*len(nums) #紀錄右到左的總乘積
        #由右到左求每個數的「右」邊乘積和
        for i in range(len(nums)-2,-1,-1):
            tmp[i]=nums[i+1]*tmp[i+1]
        #整合
        for i in range(len(nums)):
            res[i]*=tmp[i]
        return res

result = Solution()
ans = result.productExceptSelf(nums=[1,2,3,4])
print(ans)

## Python: Sol2
* follow up:
* time: O(n)
* space: **O(1)**
* 透過先前紀錄的res，將res中的元素逐次乘以一變數product，product初始值為1，之後該變數逐次乘上nums陣列中相對位置的值

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1]*len(nums)
        for i in range(1,len(nums)):
            res[i]=nums[i-1]*res[i-1]
        product=1 #存右到左num[i]累乘
        for i in range(len(nums)-1,-1,-1):
            res[i]*=product
            product*=nums[i]
        return res

## C++: Sol1
* time、space: O(n)

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

## C++: Sol2
* time: O(n)、space:O(1)

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