【Leet Code】238. Product of Array Except Self---Medium_leetcode238

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 of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

思路：

此题目有一个很简单的解法：将所有的元素相乘得到值total，然后对结果数组求值的时候只需要用total除以原数组中对应的元素，但是题目规定不允许用除法，所以需要另寻他法。

两次遍历数组，第一次将前面相乘的结果存入结果数组中，然后第二次再将后面相乘的值与前面相乘的结果相乘并存入最终的结果数组中。

代码实现：

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