LeetCode238 除自身以外数组的乘积

发表于 | 分类于 |
字数统计: 291 | 阅读时长 ≈ 1

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

题面

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

解法

由于题目要求不使用除法
其实就可以考虑前缀积的做法了
正向扫一遍反向扫一遍
然后两端乘起来就好了

但是要求不使用多余的空间，所以这里用到一个trick
用left和right表示从左向右的积和反向的积
然后每次左边的时候就正常乘 乘右边的时候等右边算完了再乘
也就是等右边的乘积算出来了再去更新output[i]的值

做法见代码吧，说得可能没有代码清楚

算是一个trick吧，也是学到了，有时候多考虑反向

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int left = 1, right = 1;
        int n = nums.size();
        vector<int> output(n, 1);
        for (int i  = 0; i < n; i++) {
            output[i] *= left;
            left *= nums[i];
            output[n - i - 1] *= right;
            right *= nums[n - i - 1];
        }     
        return output;

    }
};