y总管这个叫前后缀分解，那我就这么记好了

例题：除自身以外数组的乘积

• 链接：LeetCode238.除自身以外数组的乘积

思路

题目要求不能使用除法，所以我们不能直接把全部的积求出来再除以每个元素

我们可以考虑构建一个前缀数组prefix和一个后缀数组suffix
其中：
    prefix[i]表示第i个元素左侧所有元素的乘积
    suffix[i]表示第i个元素右侧所有元素的乘积

注意：计算前后缀数组的时候prefix[0]和suffix[n-1]都需要置为1，方便后续计算的同时也能统一处理边界情况

求答案的时候只需要遍历一遍数组，res[i] = prefix[i] * suffix[i]即可

Java代码

• 朴素版本

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] p = new int[n];
        int[] s = new int[n];
        p[0] = s[n-1] = 1;
        for(int i = 1; i < n; i++){
            p[i] = p[i-1] * nums[i-1];
        }

        for(int i = n-2; i >= 0; i--){
            s[i] = s[i+1] * nums[i+1];
        }

        int[] res = new int[n];
        for(int i = 0; i < n; i++){
            res[i] = p[i] * s[i];
        }
        return res;
    }
}

• 其实用一个数组也能出答案，只需要第二次遍历的时候倒序，一边记录答案一边更新后缀数组的值

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] p = new int[n];
        p[0] = 1;
        for(int i = 1; i < n; i++){
            //这里num[i-1]表示p[i]存储的是0到i-1的前缀积
            p[i] = p[i-1] * nums[i-1];
        }

        for(int i = n-1, s = 1; i >= 0; i--){
            p[i] *= s;
            s *= nums[i];
        }

        return p;
    }
}