Leetcode 238.除自身以外数组的乘积

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

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

• 标签：数组、前缀和

• 难度：中等

描述：给定一个数组 nums。

要求：返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

说明：

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

• 请不要使用除法，且在 O(n) 时间复杂度内解决问题。

• 进阶：在 O (1) 的额外空间复杂度内完成这个题目。

• 2 <= nums.length <= 10⁵⁰

• -30 <= nums[i] <= 30

示例：

• 示例1

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

• 示例2

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

思路

使用2次遍历：

1. 先构造一个长度和nums数组长度相同的answer数组。

2. 第一次遍历从左向右，将 nums[i] 左侧的前缀元素乘积累积起来，记录在 answer 数组中。

3. 第二次遍历从右向左，将 nums[i] 右侧的前缀元素乘积累积起来，然后与 answer 数组中记录 nums[i] 的左侧前缀元素乘积，即答案等于nums中除 nums[i] 之外其余各元素的乘积。

public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int product = 1;
        // 从左向右扫描数组，记录数组左边的前缀积
        for(int i = 0; i < n; i++) {
                answer[i] = product;
                product *= nums[i];
        }
        // 从右向左扫描数组，将数组左边的前缀积 * 右边的前缀积相乘得到最终答案
        product = 1;
        for (int i = n - 1; i >= 0; i--) {
                answer[i] *= product;
                product *= nums[i];
        }
        return answer;
}