Product of Array Except Self

lc 238

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

这个题的解法与trapping rainingwater的第一个简单做法一样，就是两个array，一个存左边相乘的结果，一个存右边所有元素相乘的结果，然后最后结果就是左边乘以右边久可以了 解法一：

O(n).

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        left[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            left[i] = nums[i] * left[i - 1]; 
        }
        int[] right = new int[nums.length];
        right[nums.length - 1] = nums[nums.length - 1];
        for(int i = nums.length- 2; i >= 0; i--){
            right[i] = right[i + 1] * nums[i];
        }
        int[] res = new int[nums.length];

        for(int i = 1; i < nums.length - 1; i++){
            res[i] = left[i - 1] * right[i + 1];
        }
        res[0] = right[1];
        res[nums.length - 1] = left[nums.length - 2];
        return res;
    }
}

该题空间上还能优化 思路上一样，但是优化了空间

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums== null || nums.length == 0) return nums;
        int length = nums.length;
        int[] res = new int[length];
        res[0] = 1;
        for (int i = 1 ; i < length; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int r = 1;
        for (int i = length - 1 ; i >= 0; i--) {
            res[i] = res[i] * r;
            r = r * nums[i];
        }

        return res;
    }
}