Leetcode 题目解析之 Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that outputi is equal to the product of all the elements of nums except numsi.

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

可以定义两个辅助数组，left和right。

lefti：存放numsi之前的乘积

righti：存放numsi之后的乘积

但是分析一下，空间可以优化，因为我们先从右向左算，再从左向右算，只需要返回的那一个数组就够了。

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