知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 除自身以外数组的乘积 ## 题目(LeetCode 238) 给定数组 nums,返回数组 answer,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。不能用除法,要求 O(n)。 ``` 输入:[1, 2, 3, 4] 输出:[24, 12, 8, 6] ``` ## 大白话理解 answer[i] = 左边所有数的乘积 × 右边所有数的乘积。 ``` nums: [1, 2, 3, 4] 左前缀积:[1, 1, 2, 6] (不含自身) 右后缀积:[24, 12, 4, 1] (不含自身) 结果: [24, 12, 8, 6] 左 × 右 ``` ## 代码 ```java public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; // 第一遍:从左到右,算左前缀积 answer[0] = 1; for (int i = 1; i < n; i++) { answer[i] = answer[i - 1] * nums[i - 1]; } // 第二遍:从右到左,乘上右后缀积 int rightProduct = 1; for (int i = n - 1; i >= 0; i--) { answer[i] *= rightProduct; rightProduct *= nums[i]; } return answer; } ``` 两遍遍历,第一遍算左边的乘积存到 answer,第二遍用一个变量累积右边的乘积乘上去。空间 O(1)(answer 不算额外空间)。 ## 复杂度 - 时间:O(n) - 空间:O(1) ## 一句话总结 左前缀积 × 右后缀积。两遍遍历,一个变量搞定右边。 --- 上一篇:[03 - 连续数组](./03-contiguous-array.md) | 下一篇:[05 - 和可被K整除的子数组](./05-subarray-div-by-k.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入