LeetCode HOT100 - 除了自身以外数组的乘积

不能使用除法，那么分析要求等价于什么

如果不除，那么就是前后区间的元素乘积

可以使用前缀和来维护，这样可以 O(1) 得到我们想要的结果

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& a) {
        int n = a.size();
        vector<int> pre(n + 1), suf(n + 1);
        pre[0] = 1;
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] * a[i];
        }
        suf[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] * a[i];
        }
        auto ans = a;
        for (int i = 0; i < n; i++) {
            ans[i] = pre[i] * suf[i + 1];
        }
        return ans;        
    }
};