题解 | #乳牛各类产奶统计#

知识点：前缀和

思路：思考一下，比如 5 8 3 1，想求出8以外的其他乘积的和

如果遍历每个数组去求，那么求5，求8，都会重复遍历3和1，

算法无非是空间换时间，那么我们就把这个值3和1，存储起来

再思考一下，想要得到8之外的元素的乘积，无非就是8前面的元素乘积 * 8后面的元素的乘积

没错，这就是前缀和，是一个数组，存储前面元素的乘积或者累积

编程语言：java

import java.util.*;


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

        //前缀和*后缀和
        for (int i = 0; i < milk_amount.length; i++) {
            res[i] = res[i] * pre[i];
        }
        return res;
    }
}