標簽：#數組 #前綴和

Ⅰ. 題目

給你一個整數數組 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)，輸出數組不算進空間復雜度中，因此我們只需要常數的空間存放變量。