稀碎从零算法笔记Day38-LeetCode:除自身以外数组的乘积

题型：数组、前缀、分治、

链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

来源：LeetCode

题目描述

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

（因为除法直接：累乘 ÷ 当前值就行了。。。）

题目样例

示例 1:

输入: nums = [1,2,3,4]y
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

题目思路

用除法很简单（没什么用）

如果用本题要考察的知识点：前/后缀的话，那么【除自己以外数组的乘积】就是这个元素【左边所有数的乘积】*【右边所有数的乘积】（需要两个for循环，2N的时间）。

原理很简单，其实实现起来也不难：以【左边的乘积】为例子，从index为1的数字（因为0下标左边没有数）开始，可以创一个大小为n的数组，接收对应的【累乘】。
【右边的乘积】亦可以创一个vector，最后遍历一下更新到一种一个数组中即可。笔者这里用了一个临时变量来接收 i 右边的数字的累乘，少创了一个动态数组。

C++代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 两个辅助数，一个表示index左边的数的累乘，一个表示index右边的数的累乘
        vector<int> left(nums.size());
        vector<int> right(nums.size());
        left[0] = 1,right[nums.size()-1] = 1;
        // 先处理left
        for(int i=1 ; i<nums.size() ; ++i)
            left[i] = left[i-1] * nums[i-1]; 

        // 再处理right
        for(int i=nums.size()-2 ; i>=0 ; --i)
            right[i] = right[i+1] * nums[i+1];

        // 修改原来数组
        for(int i=0;i<nums.size();++i)
            nums[i] = left[i] * right[i];
        return nums;
    }
};