代码训练LeetCode(24)数组乘积

代码训练(24)LeetCode之数组乘积

Author: Once Day Date: 2025年6月5日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 238. 除自身以外数组的乘积 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

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

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位 整数范围内

示例：

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

2. 分析

我们需要计算一个数组 answer，其中每个元素 answer[i] 是原数组 nums 中除了 nums[i] 之外所有元素的乘积。关键点是我们不能使用除法，并且需要在 O(n) 时间复杂度内解决，同时尽量减少额外空间的使用。

题目提供了一个数组 nums，要求我们为每一个元素计算出它所有其他元素的乘积。使用除法的话会非常直接，但题目要求我们不能使用除法，因此我们需要找到其他方法。由于每个元素的结果是其他元素的乘积，我们可以将问题分解为两部分的乘积：当前元素左侧的所有元素的乘积和右侧所有元素的乘积。

解题思路

1. 构建左积数组 L，其中 L[i] 表示 nums[i] 左侧所有元素的乘积。
2. 构建右积数组 R，其中 R[i] 表示 nums[i] 右侧所有元素的乘积。
3. 计算结果数组 answer，其中 answer[i] = L[i] * R[i]。

分析步骤

构建左积数组：

• 初始化 L[0] = 1（因为第一个元素左边没有元素）。
• 从左到右遍历 nums，每个 L[i] = L[i - 1] * nums[i - 1]。

构建右积数组：

• 初始化 R[n-1] = 1（因为最后一个元素右边没有元素）。
• 从右到左遍历 nums，每个 R[i] = R[i + 1] * nums[i + 1]。

计算结果数组：

• answer[i] = L[i] * R[i]。

举例分析，以示例 nums = [1,2,3,4]：

构建 L:

• L[0] = 1
• L[1] = 1 (L[0] * nums[0])
• L[2] = 2 (L[1] * nums[1])
• L[3] = 6 (L[2] * nums[2])

构建 R：

• R[3] = 1
• R[2] = 4 (R[3] * nums[3])
• R[1] = 12 (R[2] * nums[2])
• R[0] = 24 (R[1] * nums[1])

结果 answer:

• answer[0] = L[0] * R[0] = 1 * 24 = 24
• answer[1] = L[1] * R[1] = 1 * 12 = 12
• answer[2] = L[2] * R[2] = 2 * 4 = 8
• answer[3] = L[3] * R[3] = 6 * 1 = 6

性能优化关键点

• 时间复杂度：O(n)。我们只需要三次遍历整个数组。
• 空间复杂度：可以优化到 O(1)（不包括输出数组）。我们可以直接在输出数组上构建 L，然后用一个变量来跟踪右边元素的乘积。

3. 代码实现

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int i;*returnSize = numsSize;int *returnArray = malloc(numsSize * sizeof(int));// Build the answer array as left product arrayreturnArray[0] = 1;for (i = 1; i < numsSize; i++) {returnArray[i] = returnArray[i - 1] * nums[i - 1];}// Modify the answer array by multiplying with right productsint right = 1;for (i = numsSize - 1; i >= 0; i--) {returnArray[i] = returnArray[i] * right;right *= nums[i];}return returnArray;
}

4. 总结

这道题测试了对数组操作和优化的理解。通过空间复杂度优化，我们学习了如何利用已有的资源（输出数组和变量）减少空间需求。要提升编程能力，关键在于练习如何将问题分解成小的部分，并高效地解决它们。此外，学习如何通过一些小技巧（如变量跟踪）在有限的资源下完成任务也是很重要的。