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
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] prefixProducts = new int[nums.length];
        int[] suffixProducts = new int[nums.length];
        Arrays.fill(prefixProducts, 1);
        Arrays.fill(suffixProducts, 1);
        for (int i = 1; i < nums.length; i++) {
            prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
            suffixProducts[nums.length - i - 1] = suffixProducts[nums.length - i] * nums[nums.length - i];
        }

        int[] answer = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            answer[i] = prefixProducts[i] * suffixProducts[i];
        }
        return answer;
    }
}

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;
    }
}

References

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