leetcode 238 Product of Array Except Self
z
 2018-03-12 19:31:06  

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        
        int left = 1;
        int[] ans = new int[nums.length];
        ans[0] = 1;
        for(int i=1; i<nums.length; i++){
            ans[i] = left * nums[i-1];
            left = ans[i];
        }
        int right = 1;
        for(int i=nums.length-1; i>=0; i--){
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
}

  • left从左开始，保存当前一个数左边的数的乘积

  • right从右边开始，保存当前一个数右边的数的乘积

  • 连着合体即可

    ​ 1 2 3 4

    left 1 1*2 1*2*3

    right 4*3*2 4*3 4

  • 注意ans[0]需要初始化为1，不然ans[0]将会等于0；