题解 | #牛群重量积#

知识点：数组 前缀和

思路：不让使用除法，又需要是on复杂度，那就使用前缀和吧

前缀和基本思想：利用累加和将计算区间和的复杂度从on降低到o1

这题需要用前缀和后缀两个数组

首先理解一下前缀和后缀和，比如要求一个数组除自己之外的乘积，

那么前缀和以及后缀和都是差值少村一个自身，比如求3，那么前缀和，就是1*2 后缀和就是 4*5，显而易见，相乘就是

除去自身以外的乘积。

那么题目要求除去自身之外，还要求自身的前后两个；那么只需要改版一下即可。

还是3，那么前缀取对应前一个数，存储的是1，后缀存储取对应后一个数，存储的是5，排除 2 3 4

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型一维数组
     */
    public int[] productExceptSelf (int[] nums) {
        // write code here
        int pre[] = new int[nums.length + 2];
        int post[] = new int[nums.length + 2];
        pre[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        post[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            post[i] = post[i + 1] * nums[i + 1];
        }

        int result[] = new int[nums.length];
        for (int i = 0; i < result.length; i++) {
            //处理边界
            if (i - 1 < 0)
                result[i] = pre[i] * post[i + 1];
            if (i + 1 >= nums.length)
                result[i] = pre[i - 1] * post[i];
            if (i - 1 >= 0 && i + 1 < nums.length)
                result[i] = pre[i - 1] * post[i + 1];
        }
        return result;
    }
}