LeetCode238_除自身以外数组的乘积

标签：#数组 #前缀和

Ⅰ. 题目

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

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

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

Ⅱ. 示例

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

· 示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

0. 个人方法一：暴力循环嵌套

看到这题，第一想法就是先循环算所有数的乘积，然后再循环分别在每个位置上做个除法。但是题目直接就说不要使用除法。（我*****）（但这样也有道理：因为如果数组包含“0”的话就会有些问题）

于是我就想暴力循环了，对于每个位置都做一遍循环来计算结果。但这样时间复杂度太高了，达到了O(n²)，于是它给我报了个RunTimeError。来大概看一下吧。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> answer(length, 1);
        int MultiCount = 1;

        for (int i=0; i<length; i++)
        {
            for (int j=0; j<length; j++)
            {
                if (j != i)
                {
                    MultiCount *= nums[j];
                }
            }
            answer[i] = MultiCount;
            MultiCount = 1;
        }
        return answer;
    }
};

0. 个人方法二：前缀和后缀分别求积

在跟ChatGPT要了个思路（但没要代码）之后，它告诉我了这个前缀积+后缀积的方法。然后我猛拍大腿，我怎么没想到！于是自己实现了一下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> answer(length);
        answer[0] = 1;

        // 前缀乘积
        for (int i=1; i<length; i++)
        {
            answer[i] = answer[i-1] * nums[i-1];
        }

        // 后缀乘积
        int MultiCount = 1;
        for (int i=length-2; i>=0; i--)
        {
            MultiCount *= nums[i+1];
            answer[i] *= MultiCount;
        }

        return answer;
    }
};

• 复杂度分析

  • 时间复杂度：O(N)，其中 N 指的是数组 nums 的大小。分析与方法一相同。
  • 空间复杂度：O(1)，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。