[LeetCode] 238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

除本身之外的数组之积。

题意是给一个数组，请输出一个等长的数组，res[i] 位上存的是 input 数组除了 i 位其他所有数字的乘积。

注意这个题不能用除法，如果用除法会很简单。思路是对于在 i 位上的数字，在 res[i] 上存住从左往右把之前每个数字相乘的乘积 * 从右向左在 i 之后每个数字相乘的乘积。注意左边和右边的代码稍有不同，需要多体会。

时间O(n)

空间O(1) - output不算额外空间

Java实现

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

按照上面这个代码我跑一个例子看一下这个代码实现的整个过程

nums = [1,2,3,4], res = [0, 0, 0, 0]

经过第五行的 for loop 之后，res = [1, 1, 2, 6]

再从右往左扫描，一开始right = 1

res = [1, 1, 2, 6], right = 4

res = [1, 1, 8, 6], right = 12

res = [1, 12, 8, 6], right = 24

res = [24, 12, 8, 6], right = 24

Java另一种比较好记的写法，参考了这个帖子。大体思路是把最后的 res 数组转化为矩阵进行处理。

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

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    var left = 1;
    var product = [];
    for (let num of nums) {
        product.push(left);
        left = left * num;
    }

    var right = 1;
    for (var i = nums.length - 1; i >= 0; i--) {
        product[i] *= right;
        right *= nums[i];
    }
    return product;
};

LeetCode 题目总结