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

链接：https://leetcode-cn.com/problems/product-of-array-except-self/

class Solution {
    public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result;
        result.resize(nums.size());
        int sum = 1;
        //[1,2,3,4]
        //[1,1,2,6]
        for(int i = 0; i < nums.size(); ++i) {
            result[i] = sum; // 存储i之前index的累乘
            sum *= nums[i]; // 累乘
        }
        sum = 1;
        //[1,2,3,4]
        //[1,1,2,6]
        //[24,12,8,6]
        for(int i = nums.size() - 1; i >= 0; --i) {
            result[i] *= sum; //用i之前的累乘 * i之后的累乘
            sum *= nums[i]; // 获得i之后的累乘
        }
        return result;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中 NN 指的是输入数组的大小。
• 空间复杂度：O(1)，问题的描述中说明了输出数组不算空间复杂度。