238 除自身以外数组的乘积
暴力解法(超时)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans;
for(int i = 0; i < n; i++){
int res = 1;
for(int j = 0; j < i; j++){
res *= nums[j];
}
for(int j = i + 1; j < n; j++){
res *= nums[j];
}
ans.push_back(res);
}
return ans;
}
};
时间复杂度:\(O(n^2)\)
空间复杂度:\(O(n)\)
动态规划
类似于前缀和的思路,我们计算前缀乘积和后缀乘积
那么nums[i]除自身以外的乘积为pre[i] * suf[i]
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> pre(n + 1, 1);
vector<int> suf(n + 1, 1);
vector<int> ans;
for(int i = 1; i < n; i++)
pre[i] = pre[i - 1] * nums[i - 1];
for(int i = n - 2; i >= 0; i--)
suf[i] = suf[i + 1] * nums[i + 1];
for(int i = 0; i < n; i++){
int res = pre[i] * suf[i];
ans.push_back(res);
}
return ans;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)
双指针
思路:
在动态规划做法中,我们使用了前缀乘积和后缀乘积,我们知道前缀和可以优化为一个变量,前缀乘积和后缀乘积同理
- 前缀乘积:i从左到右遍历,pre *= nums[i]
- 后缀乘积:j从右到左遍历,suf *= nums[j]
- 在\(O(n)\)时间复杂度内完成,意味着i和j在一个循环内移动,也就是异侧双指针
- 我们将问题分解:
- 元素nums[i]右边元素的乘积,也就是ans[i] *= suf
- 元素nums[i]左边元素的乘积,也就是ans[i] *= pre
- 在一个循环内完成,因此有ans[left] *= pre,ans[right] *= suf (left从0到n - 1,right从n - 1到0),也就是left和right分别遍历一遍数组就能完成计算
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n,1);
int pre = 1, suf = 1;
// left < n && right >= 0可简化为left < n 或 right >= 0
for(int left = 0, right = n - 1; left < n && right >= 0; left++, right--){
ans[left] *= pre;
ans[right] *= suf;
pre *= nums[left];
suf *= nums[right];
}
return ans;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(1)\)