题目解析

238. 除自身以外数组的乘积

算法讲解

我们可以使用两个空间保存当前位置的左边积和右边积，需要注意的地方初始的dp表需要初始化为1，如果是0则无法得到结果，因为此处是乘法

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //前缀积  和 后缀积
        vector<int>ret;
        vector<int>l_dp(nums.size()+1, 1);
        vector<int>r_dp(nums.size()+1, 1);
        //填表
        for(int i = 1; i < nums.size(); i++)l_dp[i] = l_dp[i-1] * nums[i-1];
        for(int i = nums.size()-2; i>= 0; i--)r_dp[i] = r_dp[i+1] * nums[i+1];
        //返回结果
        for(int i = 0; i < nums.size(); i++)ret.push_back(l_dp[i] * r_dp[i]);
        return ret;
    }
};