238. 除自身以外数组的乘积
238. 除自身以外数组的乘积
题目
Given an integer array nums
, return an array answer
such thatanswer[i]
is equal to the product of all the elements of nums
exceptnums[i]
.
The product of any prefix or suffix of nums
is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n)
time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
- The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1)
extra space complexity? (The output array does not count as extra space for space complexity analysis.)
题目大意
给定一个数组 nums
。要求返回数组 answer
,其中 answer[i]
等于 nums
中除 nums[i]
之外其余各元素的乘积。
解题思路
两次遍历
构造一个答案数组 res
,长度和数组 nums
长度一致。
先从左到右遍历一遍 nums
数组,将 nums[i]
左侧的元素乘积累积起来,存储到 res
数组中。
再从右到左遍历一遍,将 nums[i]
右侧的元素乘积累积起来,再乘以原本 res[i]
的值,即为 nums
中除了 nums[i]
之外的其他所有元素乘积。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组的长度,需要遍历数组两次。 - 空间复杂度:
O(n)
,使用了一个数组来存放最终的结果。
代码
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
const n = nums.length;
let res = [];
let left = 1;
for (let i = 0; i < n; i++) {
res[i] = left;
left *= nums[i];
}
let right = 1;
for (let i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
42 | 接雨水 | [✓] | 栈 数组 双指针 2+ | |
152 | 乘积最大子数组 | [✓] | 数组 动态规划 | |
265 | 粉刷房子 II 🔒 | 数组 动态规划 | ||
2163 | 删除元素后和的最小差值 | 数组 动态规划 堆(优先队列) | ||
2906 | 构造乘积矩阵 | 数组 矩阵 前缀和 |