题意:给一个序列nums,要求返回一个序列ans,两序列元素个数相同,ans第i个元素就是除了nums[i]之外所有的数相乘之积。
思路:时间O(n),额外空间O(0)。
第一次扫一遍,处理nums[0~i-1]的积作为ans[i],这样的ans[i]就得到了i之前所有数之积,那么只剩下i后面所有数之积。
第二次从后往前扫,跟第一次的做法一样,但是这次得开个临时变量存储积了。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ans(nums.size(),);
if(nums.size()==) return ans;
for(int i=; i<nums.size(); i++) ans[i]=ans[i-]*nums[i-]; //i之前的部分先乘 int sum=;
for(int i=nums.size()-; i>=; i--) //i后面部分用个变量sum存。
{
sum*=nums[i+];
ans[i]*=sum;
}
return ans;
}
};
AC代码