【leetcode100-016】【数组】除自身以外数组的乘积

【题干】

给你一个整数数组?nums，返回?数组?answer?，其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘积?。

题目数据?保证?数组?nums之中任意元素的全部前缀元素和后缀的乘积都在??32 位?整数范围内。

请?不要使用除法，且在?O(n)?时间复杂度内完成此题。

进阶：你可以在?O(1)?的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组?不被视为?额外空间。）

【思路】

• 看到不能用除法+O（n），基本上一眼前后缀了，题目给的提示也挺明显的。
• 进阶提示也给得很明显，让你直接在输出数组操作的意思。
• 显然，res[i]=nums[i]前缀积*nums[i]后缀积，两轮遍历即可解决问题：

1. 正向遍历逐个计算当前前缀积，存入res；
2. 反向遍历逐个计算当前后缀积，和res中的前缀积相乘得到结果；
3. 考虑边界处理时，想到第i轮中真正需要存入的其实是nums[i-1]的信息，因此将nums[-1]初始化为1（实际操作是将k初始化为1）即可避免单独的边界处理，反向同理。

【题解】

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int k = 1;
        for(int i = 0; i < res.length; i++){
            res[i] = k;
            k = k * nums[i]; // 此时数组存储的是除去当前元素左边的元素乘积
        }
        k = 1;
        for(int i = res.length - 1; i >= 0; i--){
            res[i] *= k; // k为该数右边的乘积。
            k *= nums[i]; // 此时数组等于左边的 * 该数右边的。
        }
        return res;
    }
}