238. Product of Array Except Self

解題思路

分別算出從前與從後算到該 index 的乘積，最後再相乘到 output 。

程式碼

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int prefix[100001] = {0}, suffix[100001] = {0};
        int pre = 1;
        for(int i=0; i<nums.size(); i++)
        {
            prefix[i] = pre * nums[i];
            pre = prefix[i];
        }
        int suf = 1;
        for(int i=nums.size() - 1; i>=0; i--)
        {
            suffix[i] = suf * nums[i];
            suf = suffix[i];
        }
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(i == 0)
                ans.push_back(suffix[i+1]);
            else if(i == nums.size()-1)
                ans.push_back(prefix[i-1]);
            else
                ans.push_back(prefix[i-1] * suffix[i+1]);
        }
        return ans;
    }
};