016.除自身以外数组的乘积

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 <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位 整数范围内

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

题目思路

左右乘积列表

思路

我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。

对于给定索引 i，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积。下面让我们更加具体的描述这个算法。

算法

初始化两个空数组 left 和 right。对于给定索引 i ，left[i]代表的是 i 左侧所有数字的乘积，right[i]代表的是 i 右侧所有数字的乘积。

我们需要用两个循环来填充 left 和 right 数组的值。对于数组 left，left[0]应该是 1，因为第一个元素的左边没有元素。对于其他元素：left[i] = left[i-1] * nums[i-1]。

同理，对于数组 right，right[length-1]应为 1。length 指的是输入数组的大小。其他元素：right[i] =right[i+1] * nums [i+1]。

当 right 和 left 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：left[i] * right[i]。

图解

优化

尽管上面的方法已经能够很好的解决这个问题，但是空间复杂度并不为常数。

由于输出数组不算在空间复杂度内，那么我们可以将 left 或 right 数组用输出数组来计算。先把输出数组当作 left 数组来计算，然后再动态构造 right 数组得到结果。让我们来看看基于这个思想的算法。

算法

初始化 left 数组，对于给定索引 i，left[i]代表的是 i 左侧所有数字的乘积。

构造方式与之前相同，只是我们试图节省空间，先把 left 作为方法一的 leftL 数组。

这种方法的唯一变化就是我们没有构造 right 数组。而是用一个遍历来跟踪右边元素的乘积。并更新数组 left[i]=left[i]∗right。然后 right 更新为 right=right∗nums[i]，其中变量 right 表示的就是索引右侧数字的乘积。

题解代码

/**
 * O（n）时间复杂度
 * @param nums
 * @return
 */
public int[] productExceptSelf(int[] nums) {
    // left数组用于存储当前下标左侧数的积
    int[] left = new int[nums.length];
    // right 数组用于存储当前下标右侧数的积
    int[] right = new int[nums.length];
    left[0] = 1;
    right[nums.length - 1] = 1;
    for (int i = 1; i < nums.length; i++) {
        left[i] = left[i - 1] * nums[i - 1];
    }
    for (int i = nums.length - 2; i >= 0; i--) {
        right[i] = right[i + 1] * nums[i + 1];
    }
    for (int i = 0; i < nums.length; i++) {
        nums[i] = left[i] * right[i];
    }
    return nums;
}
/**
 * O（1）时间复杂度
 * @param nums
 * @return
 */
public int[] productExceptSelf2(int[] nums) {
    int[] left = new int[nums.length];
    left[0] = 1;
    // 在left数组中记录每个下标处左侧值的积 nums：[1,2,3,4]  left：[1,1,2,6]
    for (int i = 1; i < left.length; i++) {
        left[i] = left[i - 1] * nums[i - 1];
    }
    // 从右往左遍历left数组，并且使用变量right记录当前下标右侧值的积
    int right = 1;
    for (int i = nums.length - 1; i >= 0; i--) {
        // 最终的结构 = 左侧数的积 * 右侧数的积
        left[i] = left[i] * right;
        // 计算下个下标右侧数的积
        right *= nums[i];
    }
    return left;
}