LeetCode 热题 100_除自身以外数组的乘积(16_238_中等_C++)(前缀之积；后缀之积)

题目描述：

给你一个整数数组 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]

提示：
2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

题解：

解题思路：

思路一（暴力破解法(双重循环)）：
1、题目要求除自身以外数组的乘积。我们可以对每个元素除这个元素外的乘积都算一遍。

2、具体思路如下：
① 第一重循环代表除 nums[i] 之外其余各元素的乘积。
② 第二重循环用于计算各元素的乘积。
③ 这里可以考虑优化，当除自身以外数组的乘积为0元素时，计算0下标位置元素下标以外数组的乘积，其他数组的乘积设为0。
例
如nums=[-1,1,0,-3,3]，在计算第一个位置以外数组的乘积时，当乘到0时乘积为0，记录此时0的下标，计算0下标以外数组的乘积放在此位置ans=0,0,9,0,0，其余其他数组的乘积设为0。

2、复杂度分析：
① 时间复杂度：O(N²)，N代表数组的长度，使用了双重循环所以为O(N²)。
② 空间复杂度：O(1)，我们只需常数空间存放若干变量。

思路二（左右乘积列表）：
1、运用 前缀之积*后缀之积=除自身以外数组的乘积。这里我们可以先求得前缀之积和后缀之积最后再相乘。(前缀之积代表此元素之前的乘积，后缀之积代表此元素之后的乘积)。
例：nums = [1,2,3,4]
前缀之积=[1,1,2,6]
后缀之积=[24,12,4,1]
除自身以外数组的乘积=[24,12,8,6]
注意：第一个元素的前缀之积是1，最后一个元素的后缀之积也是1。

2、复杂度分析
① 时间复杂度：O(N)，其中 N 是数组中的元素数量。因遍历3遍数组。
② 空间复杂度：O(N)，其中 N 是数组中的元素数量。创建两个额外的容器存放前缀之积和后缀之积。

思路三（优化左右乘积列表）：
1、我们可以先使用ans返回答案的vector来存储前缀之积，然后使用一个变量来代表从后向前求得的后缀之积，我们在求出后缀之积的同时可以计算除自身以外数组的乘积，来存储到ans中。

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

代码实现（思路一（暴力破解法（双重循环）））：

#include<iostream>
#include<vector>
using namespace std;

vector<int> productExceptSelf1(vector<int>& nums) {
	vector<int> ans(nums.size());
	for(int i=0;i<nums.size();i++){
		int mul=1;
		for(int j=0;j<nums.size();j++){
			if(j==i){
				continue;
			}
			mul=mul*nums[j];
			if(mul==0){
				int mul2=1;
				for(int n=0;n<nums.size();n++){
					if(n==j){
						continue;
					}
					mul2=mul2*nums[n];
				}
				ans[j]=mul2;
				return ans;
			}
		}
		ans[i]=mul;
	}
    return ans; 
}

int main(){ 
	vector<int> nums={2,4,1,3,5};
	vector<int> ans=productExceptSelf1(nums);
	for(const auto &t:ans){
		cout<<t<<" "; 
	}
	return 0;
}

代码实现（思路二（左右乘积列表））：

#include<iostream>
#include<vector>
using namespace std;

vector<int> productExceptSelf2(vector<int>& nums){
	vector<int> ans(nums.size(),0);
	vector<int> L(nums.size(),0),R(nums.size(),0);
	L[0]=1;
	R[nums.size()-1]=1;
	
	//前缀之积
	for(int i=1;i<nums.size();++i){
		L[i]=L[i-1]*nums[i-1];
	}
	
	//后缀之积
	for(int i=nums.size()-2;i>=0;--i){
		R[i]=R[i+1]*nums[i+1];
	}
	//前缀之积*后缀之积=除自身以外数组的乘积 
	for(int i=0;i<nums.size();i++){
		ans[i]=R[i]*L[i];
		
	}
	return ans; 
}

int main(){ 
	vector<int> nums={2,4,1,3,5};
	vector<int> ans=productExceptSelf2(nums);
	for(const auto &t:ans){
		cout<<t<<" "; 
	}
	return 0;
}

代码实现（思路三（优化左右乘积列表））：

#include<iostream>
#include<vector>
using namespace std;

vector<int> productExceptSelf3(vector<int>& nums){
	vector<int> ans(nums.size(),0);
	ans[0]=1;
	//存储前缀之积
	for(int i=1;i<nums.size();++i){
		ans[i]=ans[i-1]*nums[i-1];
	}
	//end_mul存储当前遍历位置的后缀之积
	int end_mul=1;
	//先将最后一个元素除自身以外数组的乘积计算出来，因有了前缀之积，且最后一个元素的后缀之积为1
	ans[nums.size()-1]=ans[nums.size()-1]*end_mul;
	//我们在求出后缀之积的同时可以计算除自身以外数组的乘积，来存储到ans中
	for(int i=nums.size()-2;i>=0;--i){
		end_mul=end_mul*nums[i+1];
		ans[i]=ans[i]*end_mul;
	}
	return ans;
}

int main(){ 
	vector<int> nums={2,4,1,3,5};
	vector<int> ans=productExceptSelf3(nums);
	for(const auto &t:ans){
		cout<<t<<" "; 
	}
	return 0;
}

LeetCode 热题 100_除自身以外数组的乘积(16_238)原题链接

欢迎大家和我沟通交流(✿◠‿◠)