238. Product of Array Except Self [Medium]

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.

Constraints:

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

Example

Input: nums = [2,3,4,5]
Output: [60,40,30,24]

思路

input -> [2,3,4,5]
res   -> [1,1,1,1]
----------------------
先缓存从左向右自乘的结果，这个时候24就是前三位相乘结果
res   -> [1,2,6,24]
24已经是结果了，跳过最后一位
temp -> 5
	    5*6=30
res  -> [1,2,30,24]
----------------------
temp ->  5*4=20
	 20*2=40
res  -> [1,40,30,24]
----------------------
temp -> 20*3=60
      60*1=60
res  -> [60,40,30,24]

题解

• 无脑

    //根据上述思路快速写了一版
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, 1);
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int temp = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i == nums.length - 1) {
                temp = nums[i];
            } else {
                res[i] *= temp;
                temp *= nums[i];
            }
        }
        return res;
    }

• 优化

    // 感觉有点在找规律，凑值，有点恶心，精简一下，用前缀后缀来暂存值
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int prefix, postfix;
	// res[0] 赋值为1，是因为int默认值是0，下面给res赋值时后会出错
        prefix = postfix = res[0] = 1;
	// 跳过第一位
        for (int i = 1; i < nums.length; i++) {
            prefix *= nums[i - 1];
	// [1,2,30,24] 这个时候最后一位结果已经出来了
            res[i] = prefix;
        }
	// 所以从倒数第二位开始
        for (int i = nums.length - 2; i >= 0; i--) {
	    // postfix[60,5,20,1] 拿这些后缀值去和res相乘得到最终结果
            postfix *= nums[i + 1];
            res[i] *= postfix;
        }
        return res;
    }