1. 问题背景与核心挑战今天要讨论的是LeetCode热题HOT100中的一道经典数组操作题目——除自身以外数组的乘积。这道题在面试中出现频率极高考察的是对数组遍历和空间复杂度的掌控能力。题目要求我们给定一个整数数组nums返回一个数组answer其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。这个问题的难点在于不能使用除法运算题目明确限制时间复杂度必须控制在O(n)空间复杂度除输出数组外需为O(1)进阶要求我第一次遇到这个问题时直观想到的暴力解法是对于每个元素都遍历整个数组计算乘积但这样时间复杂度会达到O(n²)显然不符合要求。后来经过反复推敲发现可以通过前缀积和后缀积的巧妙组合来优化。2. 算法思路解析2.1 前缀积与后缀积的概念解决这个问题的关键在于理解前缀积Prefix Product和后缀积Suffix Product前缀积表示数组从开始到当前元素前一个位置所有元素的乘积后缀积表示从当前元素后一个位置到数组末尾所有元素的乘积以数组[1,2,3,4]为例对于元素2索引1其前缀积是1后缀积是3×412对于元素3索引2其前缀积是1×22后缀积是42.2 空间优化策略最直观的解法是分别计算并存储每个元素的前缀积和后缀积然后将两者相乘得到最终结果。但这样需要额外的两个数组空间复杂度为O(n)。进阶解法通过复用输出数组来实现O(1)空间复杂度不考虑输出数组先用输出数组存储前缀积再用一个变量动态计算后缀积同时更新输出数组3. 具体实现步骤3.1 基础实现空间复杂度O(n)def productExceptSelf(nums): n len(nums) prefix [1] * n suffix [1] * n answer [1] * n # 计算前缀积 for i in range(1, n): prefix[i] prefix[i-1] * nums[i-1] # 计算后缀积 for i in range(n-2, -1, -1): suffix[i] suffix[i1] * nums[i1] # 合并结果 for i in range(n): answer[i] prefix[i] * suffix[i] return answer3.2 优化实现空间复杂度O(1)def productExceptSelf(nums): n len(nums) answer [1] * n # 先用answer存储前缀积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 动态计算后缀积并更新answer suffix 1 for i in range(n-1, -1, -1): answer[i] * suffix suffix * nums[i] return answer4. 复杂度分析与边界情况4.1 时间复杂度两种实现方式都只需要两次遍历数组时间复杂度均为O(n)。4.2 空间复杂度基础实现使用了prefix和suffix两个额外数组空间复杂度O(n)优化实现仅使用常数空间存储suffix空间复杂度O(1)不考虑输出数组4.3 边界情况处理空数组直接返回空数组单元素数组返回[1]因为没有任何其他元素包含0的数组需要特别注意但题目保证乘积不会溢出32位整数范围5. 常见错误与调试技巧5.1 典型错误忘记初始化前缀/后缀数组的第一个/最后一个元素在优化实现中后缀积计算时没有正确更新suffix变量索引越界特别是在处理边界元素时5.2 调试建议对于小数组如[1,2,3,4]手动计算每一步的结果打印中间变量prefix、suffix检查是否正确特别注意循环的起始和终止条件6. 算法扩展与变种6.1 允许使用除法的情况如果题目允许使用除法可以先计算所有元素的乘积然后对于每个元素用总乘积除以当前元素。但需要注意数组中可能有0需要特殊处理题目通常明确禁止使用除法6.2 多维数组扩展这个问题可以扩展到二维矩阵计算除当前元素外所有行和列的乘积。思路类似但需要分别计算行前缀积和列前缀积。7. 实际应用场景这种算法思想在以下场景中有实际应用图像处理中的邻域计算统计学中的滑动窗口计算金融分析中的累积收益率计算8. 个人实现心得在实际编码时我发现以下几点特别重要先写出基础解法确保逻辑正确再考虑优化画图辅助理解前缀和后缀的关系对于优化解法特别注意更新变量的顺序重要提示在面试中建议先解释基础解法再提出优化思路最后实现优化解法。这能展示你的思考过程。
1. 问题背景与核心挑战今天要讨论的是LeetCode热题HOT100中的一道经典数组操作题目——除自身以外数组的乘积。这道题在面试中出现频率极高考察的是对数组遍历和空间复杂度的掌控能力。题目要求我们给定一个整数数组nums返回一个数组answer其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。这个问题的难点在于不能使用除法运算题目明确限制时间复杂度必须控制在O(n)空间复杂度除输出数组外需为O(1)进阶要求我第一次遇到这个问题时直观想到的暴力解法是对于每个元素都遍历整个数组计算乘积但这样时间复杂度会达到O(n²)显然不符合要求。后来经过反复推敲发现可以通过前缀积和后缀积的巧妙组合来优化。2. 算法思路解析2.1 前缀积与后缀积的概念解决这个问题的关键在于理解前缀积Prefix Product和后缀积Suffix Product前缀积表示数组从开始到当前元素前一个位置所有元素的乘积后缀积表示从当前元素后一个位置到数组末尾所有元素的乘积以数组[1,2,3,4]为例对于元素2索引1其前缀积是1后缀积是3×412对于元素3索引2其前缀积是1×22后缀积是42.2 空间优化策略最直观的解法是分别计算并存储每个元素的前缀积和后缀积然后将两者相乘得到最终结果。但这样需要额外的两个数组空间复杂度为O(n)。进阶解法通过复用输出数组来实现O(1)空间复杂度不考虑输出数组先用输出数组存储前缀积再用一个变量动态计算后缀积同时更新输出数组3. 具体实现步骤3.1 基础实现空间复杂度O(n)def productExceptSelf(nums): n len(nums) prefix [1] * n suffix [1] * n answer [1] * n # 计算前缀积 for i in range(1, n): prefix[i] prefix[i-1] * nums[i-1] # 计算后缀积 for i in range(n-2, -1, -1): suffix[i] suffix[i1] * nums[i1] # 合并结果 for i in range(n): answer[i] prefix[i] * suffix[i] return answer3.2 优化实现空间复杂度O(1)def productExceptSelf(nums): n len(nums) answer [1] * n # 先用answer存储前缀积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 动态计算后缀积并更新answer suffix 1 for i in range(n-1, -1, -1): answer[i] * suffix suffix * nums[i] return answer4. 复杂度分析与边界情况4.1 时间复杂度两种实现方式都只需要两次遍历数组时间复杂度均为O(n)。4.2 空间复杂度基础实现使用了prefix和suffix两个额外数组空间复杂度O(n)优化实现仅使用常数空间存储suffix空间复杂度O(1)不考虑输出数组4.3 边界情况处理空数组直接返回空数组单元素数组返回[1]因为没有任何其他元素包含0的数组需要特别注意但题目保证乘积不会溢出32位整数范围5. 常见错误与调试技巧5.1 典型错误忘记初始化前缀/后缀数组的第一个/最后一个元素在优化实现中后缀积计算时没有正确更新suffix变量索引越界特别是在处理边界元素时5.2 调试建议对于小数组如[1,2,3,4]手动计算每一步的结果打印中间变量prefix、suffix检查是否正确特别注意循环的起始和终止条件6. 算法扩展与变种6.1 允许使用除法的情况如果题目允许使用除法可以先计算所有元素的乘积然后对于每个元素用总乘积除以当前元素。但需要注意数组中可能有0需要特殊处理题目通常明确禁止使用除法6.2 多维数组扩展这个问题可以扩展到二维矩阵计算除当前元素外所有行和列的乘积。思路类似但需要分别计算行前缀积和列前缀积。7. 实际应用场景这种算法思想在以下场景中有实际应用图像处理中的邻域计算统计学中的滑动窗口计算金融分析中的累积收益率计算8. 个人实现心得在实际编码时我发现以下几点特别重要先写出基础解法确保逻辑正确再考虑优化画图辅助理解前缀和后缀的关系对于优化解法特别注意更新变量的顺序重要提示在面试中建议先解释基础解法再提出优化思路最后实现优化解法。这能展示你的思考过程。
