238. Product of Array Except Self（LeetCode）

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.)

 1 class Solution {
 2 public:
 3     vector<int> productExceptSelf(vector<int>& nums) {
 4         int sum = 1;
 5         for (int i = 0; i < nums.size(); i++)
 6         {
 7             sum *= nums[i];
 8         }
 9         if (sum == 0)
10         {
11             int count = 0;
12             int flag = 0;
13             for (int i = 0; i < nums.size(); i++)
14             {
15                 if (nums[i] == 0)
16                 {
17                     count++;
18                     flag = i;
19                 }
20             }
21             if (count == 1)
22             {
23                 int sum = 1;
24                 for (int i = 0; i < nums.size(); i++)
25                 {
26                     if (i != flag)
27                         sum *= nums[i];
28                 }
29                 for (int i = 0; i < nums.size(); i++)
30                 {
31                     if (i == flag)
32                         nums[i] = sum;
33                     else
34                         nums[i] = 0;
35                 }
36             }
37             else
38             {
39                 for (int i = 0; i < nums.size(); i++)
40                 {
41                     nums[i] = 0;
42                 }
43             }
44         }
45         else
46         {
47             for (int i = 0; i < nums.size(); i++)
48             {
49                 nums[i] = sum / nums[i];
50             }
51         }
52 
53         return nums;
54     }
55 };

如果是考试，会立刻想到上面的方法，下面的方法是别人的，在考试的状态下，我感觉没有充裕的时间，我想不到。

 1 class Solution {
 2 public:
 3     vector<int> productExceptSelf(vector<int>& nums) {
 4         int n = nums.size();
 5         int fromBegin = 1;
 6         int fromLast = 1;
 7         vector<int> res(n, 1);
 8 
 9         for (int i = 0; i<n; i++){
10             res[i] *= fromBegin;
11             fromBegin *= nums[i];
12             res[n - 1 - i] *= fromLast;
13             fromLast *= nums[n - 1 - i];
14         }
15         return res;
16 
17     }
18 };