[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：
2 <= nums.length <= $10^5$
-30 <= nums[i] <= 30
输入 保证 数组 answer[i] 在 32 位 整数范围内

知识点：
数组、前缀乘积、后缀乘积

解1（优化前）：
核心思想：用两个额外的辅助数组，存储每个位置的前缀乘积、后缀乘积。得到这两个数组后，遍历每个位置，结果值=当前位置的前缀乘积*当前位置的后缀乘积。

辅助数组的初始值，需要设为1，因为计算的是乘积，而不是和。

时间复杂度：$O(n)$。每个for循环均最多遍历1次数组。
空间复杂度：$O(n)$。使用了两个辅助数组（题目说了分析空间复杂度时，不考虑输出数组）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        //获取数组大小
        int n = nums.length;
        //定义结果数组
        int[] answer = new int[n];

        //定义辅助数组，存储前缀乘积、后缀乘积
        int[] pre = new int[n];
        int[] suf = new int[n];
        //辅助数组设置初始值（因为是乘积，所以是1）
        pre[0] = 1;
        suf[n - 1] = 1;
        //计算每个位置的前缀乘积
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        //计算每个位置的后缀乘积
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }

        //遍历每个元素，计算当前位置的结果值
        for (int i = 0; i < n; i++) {
            answer[i] = pre[i] * suf[i];
        }
        return answer;
    }
}

解2（优化后）：
核心思想：
①先计算每个位置的后缀乘积
②然后在遍历每个元素的同时，将用变量（而非数组，这里就是优化的地方）代表的前缀乘积乘到后缀乘积中
③然后再更新前缀乘积，该前缀乘积用于下个位置的判断（这样说方便理解）
由于输出数组不在空间复杂度的考虑中，因此这里的后缀数组就是最终返回的输出数组。

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。没有用额外的辅助数组。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        //获取数组大小
        int n = nums.length;
        //定义数组存储后缀乘积，并作为最后输出的结果数组
        int[] suf = new int[n];

        //数组设置初始值（因为是乘积，所以是1）
        suf[n - 1] = 1;
        //计算每个位置的后缀乘积
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }

        //遍历每个元素，边计算前缀乘积，边计算当前位置的结果值
        int pre = 1;
        for (int i = 0; i < n; i++) {
            //结果值=前缀乘积*后缀乘积，此时已有每个位置的后缀乘积，从而得到结果值
            suf[i] *= pre;
            //计算前缀乘积，用于下一个位置的判断
            pre *= nums[i];
        }
        return suf;
    }
}

参考：
1、灵神解析