238. Product of Array Except Self - Medium

前往題目

想法

• 想不出不用除法怎麼解

思路

1. 利用prefix和postfix sum
2. 先疊代一次建構prefix sum
3. 再由後往前直接建構答案

看不懂的話可以把postfix sum和prefix sum各列出來，就可以發現只要把任何一個位置的postfix以及同位置的prefix sum乘起來就是答案

Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];

        Arrays.fill(res, 1); // Fill the array with 1

        int prefix = 1;

        // Make prefix
        for (int i = 0; i < nums.length; ++i) {
            res[i] *= prefix; // except self, so 1 * prefix
            prefix *= nums[i]; // Update prefix as the index goes
        }

        int postfix = 1;

        // Going back to compensate the postfix
        for (int i = nums.length - 1; i >= 0; --i) {
            res[i] *= postfix; // except self, so 1 * postfix as well
            postfix *= nums[i]; // Update postfix
        }
        
        return res;
    }
}