跳转至

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)\)