普通数组

除了自身以外数组的乘积

中等#238Java时间 O(n)空间 O(1),不含输出

题目要做什么

返回一个数组,其中 ans[i] 是除 nums[i] 之外所有元素的乘积。不使用除法,在线性时间内完成。

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

01 为什么这样做

先把每个位置左侧的乘积写入答案,再从右往左乘上右侧乘积。零值不需要特殊处理。

始终成立的条件

第一遍 ans[i] 不包含当前位置;第二遍 right 不包含当前及其左侧元素。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int[] productExceptSelf(int[] nums) {3        int[] ans = new int[nums.length];4        int left = 1;5        for (int i = 0; i < nums.length; i++) {6            ans[i] = left;7            left *= nums[i];8        }9        int right = 1;10        for (int i = nums.length - 1; i >= 0; i--) {11            ans[i] *= right;12            right *= nums[i];13        }14        return ans;15    }16}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索