LeetCode 面试经典 150_数组/字符串_除自身以外数组的乘积（13_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
输入 保证 数组 answer[i] 在 32 位 整数范围内

题解：

解题思路：

思路一（暴力破解法）：

1、题目要求除自身以外数组的乘积。可以对每个位置除自身以外的乘积都算一遍。
例:nums = [1,2,3,4]
① 计算除 1 以外的乘积 ans=[24]
② 计算除 2 以外的乘积 ans=[24,12]
③ 计算除 3 以外的乘积 ans=[24,12,8]
④ 计算除 4 以外的乘积 ans=[24,12,8,6]
如果某一位置元素为 0 ，可计算当前位置以外元素的乘积。其余位置为0。
例：nums = [-1,1,0,-3,3]，ans=[0,0,9,0,0]

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

思路二（前缀积）：

1、例：nums = [1,2,3,4]
① 计算除 1 以外的乘积，是(1) × (2×3×4) 。注 ：(1) 是前缀积，(2×3×4) 是后缀积
② 计算除 2 以外的乘积，是(1) × (3×4)
③ 计算除 3 以外的乘积，是(1×2) × (4)
④ 计算除 4 以外的乘积，是(1×2×3) × (1)
发现除自身以外元素的乘积 = 前缀积 × 后缀积

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

代码实现

代码实现（思路一（暴力破解））：

class Solution1 {
public:// 函数定义：返回一个数组，数组中的每个元素是除了当前元素之外所有元素的乘积vector<int> productExceptSelf(vector<int>& nums) {// 创建一个与 nums 同大小的结果数组 ans 用于存储每个位置的结果vector<int> ans(nums.size());// 外层循环遍历 nums 数组的每个元素for(int i = 0; i < nums.size(); i++) {// 初始化乘积变量 mul 为 1，用于计算当前位置 i 除去 nums[i] 之外所有元素的乘积int mul = 1;// 内层循环遍历数组 nums 中的每个元素for(int j = 0; j < nums.size(); j++) {// 如果当前索引 j 等于 i，则跳过，避免计算当前元素的乘积if(j == i) {continue;}// 累乘 nums 中所有不等于当前位置 i 的元素mul = mul * nums[j];// 如果乘积为 0，则进入特殊处理流程if(mul == 0) {// 如果乘积为 0，重新计算除去当前为 0 元素外其他元素的乘积int mul2 = 1;// 再次遍历 nums 数组，计算排除 j 元素外所有其他元素的乘积for(int n = 0; n < nums.size(); n++) {// 跳过索引为 j 的元素if(n == j) {continue;}// 累乘 nums 中除去 j 索引的其他元素mul2 = mul2 * nums[n];}// 将排除 0 后的乘积存储到 ans[j]ans[j] = mul2;// 返回最终结果数组 ansreturn ans;}}// 将当前位置 i 的乘积（排除当前元素的乘积）存储到 ans[i]ans[i] = mul;}// 返回最终的结果数组 ansreturn ans; }
};

代码实现（思路二（双指针））：

class Solution {
public:vector<int> productExceptSelf(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;// 我们在求出后缀之积的同时可以计算除自身以外数组的乘积，来存储到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;}
};

以思路二为例进行调试

#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;//我们在求出后缀之积的同时可以计算除自身以外数组的乘积，来存储到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 面试经典 150_数组/字符串_除自身以外数组的乘积（13_238)原题链接
欢迎大家和我沟通交流(✿◠‿◠)