Poison

238. Product of Array Except Self

发表于
Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] prefixProductArray = new int[nums.length];
        int[] suffixProductArray = new int[nums.length];

        int prefixProduct = 1;
        for (int i = 0; i < nums.length; i++) {
            prefixProductArray[i] = prefixProduct;
            prefixProduct *= nums[i];
        }

        int suffixProduct = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            suffixProductArray[i] = suffixProduct;
            suffixProduct *= nums[i];
        }

        int[] productArray = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            productArray[i] = prefixProductArray[i] * suffixProductArray[i];
        }
        return productArray;
    }
}
Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] productArray = new int[nums.length];

        int prefixProduct = 1;
        for (int i = 0; i < nums.length; i++) {
            productArray[i] = prefixProduct;
            prefixProduct *= nums[i];
        }

        int suffixProduct = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            productArray[i] *= suffixProduct;
            suffixProduct *= nums[i];
        }

        return productArray;
    }
}
Reference

238. Product of Array Except Self
剑指 Offer 66. 构建乘积数组