题目描述
原题链接：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;
}
};