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

思路

乘积 = 当前数左边的乘积 * 当前数右边的乘积

我一开始想到了要这么去解决，但是没有想到如何用o(n) 的时间复杂度解决

看了别人的题解才明白，将这个过程分两步完成，先保留当前数左边的乘积，然后乘上当前数右边的乘积，处理两趟，就可以了。
可以从左到右遍历，就可以从右向左遍历，同时还可以将一步的过程变成两步来做，厉害哇。异步获得结果。

代码

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

总结

心力憔悴，这。。