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

问题

传送门：https://leetcode.cn/problems/product-of-array-except-self/

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

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

示例 1:

输入: nums = [1,2,3,4]
输出: [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 位 整数范围内

思路

不妨以一个具体的例子来看看结果是如何得出的。

事实上，可以发现每一个元素除开自身以外数组的乘积可以由两部分组成：该元素左侧元素和右侧元素。那么我们可以维护两个前缀积数组，存储到最左侧的元素之积以及最右侧的元素之积即可。具体地，记原数组为$nums[]$，其长度为$n$，则

• 维护$left[]$数组，其中$left[i]=nums[0]\times nums[1] \times \cdots\times nums[i-1]$
• 维护$right[]$数组，其中$right[i] = nums[i+1]\times nums[i+2]\times \cdots\times nums[n-1]$

两轮遍历，分别为left数组和right数组赋值即可。

代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int left[100005];
        int right[100005];
        int n = nums.size();
        left[0] = right[n-1] = 1;
        int i;
        for(i=1; i<n-1; i++) {
            left[i] = left[i-1] * nums[i-1];
            right[n-1-i] = right[n-i] * nums[n-i]; 
        }
        left[n-1] = left[n-2] * nums[n-2], right[0] = right[1] * nums[1];
        vector<int> ans;
        for(i=0; i<n; i++) {
            ans.push_back(left[i] * right[i]);
        }
        return ans;
    }
};