Leetcode 238. 除自身以外數(shù)組的乘積 前綴和
2021-11-01 14:23:59

地址 https://leetcode-cn.com/problems/product-of-array-except-self/

給你一個(gè)長度為?n?的整數(shù)數(shù)組?nums，其中?n > 1，返回輸出數(shù)組?output?，
其中 output[i]?等于?nums?中除?nums[i]?之外其余各元素的乘積。

示例:
輸入: [1,2,3,4]
輸出: [24,12,8,6]

提示：題目數(shù)據(jù)保證數(shù)組之中任意元素的全部前綴元素和后綴（甚至是整個(gè)數(shù)組）的乘積都在 32 位整數(shù)范圍內(nèi)。
說明: 請不要使用除法，且在?O(n) 時(shí)間復(fù)雜度內(nèi)完成此題。

進(jìn)階：
你可以在常數(shù)空間復(fù)雜度內(nèi)完成這個(gè)題目嗎？（ 出于對空間復(fù)雜度分析的目的，輸出數(shù)組不被視為額外空間。）

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/product-of-array-except-self
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解答
最基礎(chǔ)的想法是計(jì)算所有數(shù)的乘積 然后除以當(dāng)前數(shù)字就是答案
但是題目要求不使用除法，我們可以考慮使用類似前綴和的實(shí)現(xiàn)
假設(shè)兩個(gè)數(shù)組 l[] r[]，
l[i]記錄1~i所有元素的乘積
r[i]記錄nums.size()-1 ~i的逆向次序的所有元素乘積
那么整個(gè)數(shù)組的除開當(dāng)前元素的乘積就是
ans[i]=l[i-1]*r[i+1];
以題目例子為例

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

		right[nums.size() - 1] = nums[nums.size() - 1];
		for (int i = nums.size() - 2; i >= 0; i--) {
			right[i] = right[i + 1] * nums[i];
		}

		for (int i = 0; i < nums.size(); i++) {
			if (i == 0) {
				ans[i] = right[i + 1];
			}else if( i== nums.size()-1){
				ans[i] = left[i - 1];
			}else {
				ans[i] = left[i - 1] * right[i + 1];
			}
		}

		return ans;
	}
};

我的視頻題解空間