题目描述

原题链接：Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6]

给定一个长度大于1的数组，计算出一组乘积output[n]，output[i]等于这个数组里除去nums[i]的所有数的积。要求时间复杂度在O(n)内且不含除法。

思路

这一题乍一看很简单，计算出所有数的积然后分别除掉每个数就行了，但原题要求不能用除法。那么，我们就只能使用乘法了。在只使用乘法的情况下想要时间复杂度达到O(n)，则需要避免其中重复计算。

假设对于数组 nums[]={2, 3, 4, 5 }, 假设result[]为最后结果，可以得到：

result.jpg

只需要计算出A、B这两个三角形上每行的乘积，就可以得到result了。比如：

A[0]=1,A[1]=2,A[2]=2*3=6,A[3]=2*3*4=24;
B[0]=3*4*5=60,B[1]=4*5=20,B[2]=5,B[3]=1;
result[0]=A[0]*B[0],result[1]=A[1]*B[1];

以此类推。

计算A、B就简单了，完全可以在O(n)内办到。

代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    
        vector<int> result;
        vector<int> leftSum ;
        vector<int> rightSum ;
    
        if (nums.size()<2)
            return result;
    
        int leftTemp=1;
        int rightTemp=1;
        leftSum.push_back(leftTemp);
        rightSum.push_back(rightTemp);
    
        for (int i=0;i+1<nums.size();i++){
            leftTemp *= nums[i];
            leftSum.push_back(leftTemp);
        }
    
        for (int i=nums.size()-1;i>=1;i--){
            rightTemp*=nums[i];
            rightSum.push_back(rightTemp);
        }
        reverse(rightSum.begin(),rightSum.end());
    
        for (int i=0;i<leftSum.size();i++){
            result.push_back(leftSum[i]*rightSum[i]);
        }
        
    
        return result;
    }
};