238. Product of Array Except Self.md

238. Product of Array Except Self

思路

给定一个元素个数不少于2个的数组nums，要求返回一个结果数组output，要求output[i]为nums[0,...,i-1,i+1,...,n-1]共n-1个元素的乘积。题目要求不能使用除法且线性复杂度。

思路一

所以我们可以把output[i]分成两个部分相乘组成:

1. nums[0,...,i-1]共i个元素的乘积;
2. nums[i+1,...,n-1]共n-i-1个元素的乘积;

所以我们可以分别从前往后和从后往前遍历两次数组得到两个数组left和right数组，这两个数组就分别代表以上两个部分，最后再将二者相乘即可。

时间和空间复杂度均为O(n)。

思路二

仔细分析思路一可发现其空间复杂度可以继续优化：

我们没必要开辟数组来保存上述两部分而只需在从前往后和从后往前遍历时用两个累积变量left_product和right_product保存这两个值同时更新output就可以了。

优化后就变成了常数空间复杂度，时间复杂度为O(n)。

C++

思路一

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int>left(n, 1);
        vector<int>right(n, 1);
        vector<int>output(n, 1);
        
        for(int i = 1; i < n; i++)
            left[i] = left[i - 1] * nums[i - 1];
        
        for(int i = n - 2; i >= 0; i--)
            right[i] = right[i + 1] * nums[i + 1];
        
        for(int i = 0; i < n; i++)
            output[i] = left[i] * right[i];
        
        return output;
    }
};

思路二

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int>output(n);
        
        int left_product = 1;
        for(int i = 0; i < n; i++){
            output[i] = left_product;
            left_product *= nums[i];
        }
        
        int right_product = 1;
        for(int i = n - 1; i >= 0; i--){
            output[i] *= right_product;
            right_product *= nums[i];
        }
        return output;
    }
};