【力扣Problem:238. 除了自身以外数组的乘积】前后缀乘法 + 双指针优化

Problem:238. 除了自身以外数组的乘积

题目描述

给你一个整数数组 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^5
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位 整数范围内

解法一：前后缀乘法

核心思路

题目要求nums 中除了 nums[i] 之外其余各元素的乘积 ，就是求 nums[i] 左边元素乘积与右边元素乘积的乘积。 受到前缀和的启发，我们可以求 nums 数组的前后缀乘积数组，分别记为 ret_l 和 ret_r：

代码实现

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
vector<int> ret_l(n),ret_r(n);
ret_l[0] = 1,ret_r[n–1] = 1;
for(int i = 1;i < n;i++) ret_l[i] = ret_l[i–1] * nums[i–1];
for(int i = n–2;i >= 0;i—) ret_r[i] = ret_r[i+1] * nums[i+1];
for(int i = 0;i < n;i++) ans[i] = ret_l[i] * ret_r[i];
return ans;
}
};

⏱️ 时间复杂度：

O

(

N

)

O(N)

O(N) 🏠 空间复杂度：

O

(

N

)

O(N)

O(N)

解法二：双指针优化（首尾指针）

优化思路

前后缀乘积数组只用了一次，考虑用双指针边遍历边求，从而优化空间复杂度。我们用变量 ret_l = 1,ret_r = 1 代替数组：

方案 A：两次循环

• 第一次循环： 从左往右先求左侧乘积，ans[i] 表示 i 左侧元素乘积，迭代更新 ret_l;
• 第二次循环： 从右往左对 ans[i] 结果叠加上右侧乘积，并不断更新 ret_r，直到循环结束。

代码实现

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n,1);
int ret_l = 1,ret_r = 1;
for(int i = 0;i < n;i++) {
ans[i] = ret_l;
ret_l *= nums[i];
}
for(int i = n–1;i >= 0;i—) {
ans[i] *= ret_r;
ret_r *= nums[i];
}
return ans;
}
};

方案 B：单次循环优化

可以继续将两次循环和到一个循环里，只需要维护前后两指针 i,j 分别从两侧向另一侧工作即可。

代码实现

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n,1);
int ret_l = 1,ret_r = 1;
for(int i = 0,j = n–1;i < n;i++,j—) {
ans[i] *= ret_l;
ans[j] *= ret_r;
ret_l *= nums[i];
ret_r *= nums[j];
}
return ans;
}
};

⏱️ 时间复杂度：

O

(

N

)

O(N)

O(N) 🏠 空间复杂度：

O

(

1

)

O(1)

O(1)（除输出数组外）

❤️ 最后

新人up，如有不足还请多多指正，欢迎交流！ 如果内容对你有帮助的话，还请点赞支持一下喽🙏🙏 你的支持是我前进的最大动力！！ up正在更新力扣hot100的题目，有需要的朋友欢迎点赞、收藏加关注哦！