238. Product of Array Except Self

leetcode網址

問題

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

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