【力扣100题】59.除自身以外数组的乘积

题目描述给你一个整数数组nums返回数组answer其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积。题目数据保证数组nums中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法且在 O(n) 时间复杂度内完成此题。示例示例 1 输入nums [1,2,3,4] 输出[24,12,8,6] 示例 2 输入nums [-1,1,0,-3,3] 输出[0,0,9,0,0]提示2 nums.length 10^5-30 nums[i] 30输入保证数组 answer[i] 在 32 位整数范围内进阶你可以在 O(1) 的额外空间复杂度内完成这个题目吗出于对空间复杂度分析的目的输出数组不被视为额外空间。解题思路总览方法核心思想时间复杂度空间复杂度备注左右乘积最优左右夹击累乘前缀和后缀O(n)O(1)推荐解法前缀后缀数组分别计算前缀和后缀O(n)O(n)空间不优除法禁止总乘积除以自身O(n)O(1)题目禁止一、核心解法左右乘积法核心思想对于每个位置 i答案 左侧所有元素的乘积 × 右侧所有元素的乘积。nums [1, 2, 3, 4] answer[i] (nums[0] * ... * nums[i-1]) * (nums[i1] * ... * nums[n-1]) 左侧乘积 × 右侧乘积 answer[0] 1 × (2*3*4) 24 answer[1] (1) × (3*4) 12 answer[2] (1*2) × (4) 8 answer[3] (1*2*3) × 1 6 结果: [24, 12, 8, 6]算法流程图输入: nums [1, 2, 3, 4] 第一步初始化 answer 数组 answer [1, 1, 1, 1] 第二步从左向右累乘前缀乘积 i 0: answer[0] 1, left 1*1 1 i 1: answer[1] 1, left 1*2 2 i 2: answer[2] 2, left 2*3 6 i 3: answer[3] 6, left 6*4 24 answer [1, 2, 6, 24] (此时 answer[i] 左侧累乘) left 24 第三步从右向左累乘乘上右侧乘积 i 3: answer[3] * 1 24*1 24, right 1*4 4 i 2: answer[2] * 4 6*4 24, right 4*3 12 i 1: answer[1] * 12 2*12 24, right 12*2 24 i 0: answer[0] * 24 1*24 24, right 24*1 24 结果: answer [24, 12, 8, 6]二、双指针版本图解nums [1, 2, 3, 4], answer [1, 1, 1, 1] 初始化 left 1 (代表位置 0 左侧的乘积) right 1 (代表位置 n-1 右侧的乘积) l 0 (左指针) r 3 (右指针) 第一轮循环 r3 0, l0 4 answer[3] * right 1*1 1 answer[0] * left 1*1 1 left * nums[0] 1*1 1 right * nums[3] 1*4 4 l, r-- 第二轮循环 r2 0, l1 4 answer[2] * right 1*4 4 answer[1] * left 1*1 1 left * nums[1] 1*2 2 right * nums[2] 4*3 12 l, r-- 第三轮循环 r1 0, l2 4 answer[1] * right 1*12 12 answer[2] * left 4*2 8 left * nums[2] 2*3 6 right * nums[1] 12*2 24 l, r-- 第四轮循环 r0 0, l3 4 answer[0] * right 1*24 24 answer[3] * left 1*6 6 left * nums[3] 6*4 24 right * nums[0] 24*1 24 l, r-- 循环结束 (r 0) 输出: [24, 12, 8, 6]三、完整代码实现版本一左右累乘标准版classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();vectorintanswer(n,1);// 第一步从左向右累乘// answer[i] nums[0] * nums[1] * ... * nums[i-1]intleft1;for(inti0;in;i){answer[i]left;left*nums[i];}// 第二步从右向左累乘// answer[i] * nums[i1] * nums[i2] * ... * nums[n-1]intright1;for(intin-1;i0;i--){answer[i]*right;right*nums[i];}returnanswer;}};版本二双指针classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();vectorintanswer(n,1);intleft1;// 左侧累乘intright1;// 右侧累乘intl0;// 左指针intrn-1;// 右指针while(r0ln){// 先处理右指针位置乘上右侧乘积answer[r]*right;right*nums[r];// 再处理左指针位置乘上左侧乘积answer[l]*left;left*nums[l];l;r--;}returnanswer;}};四、逐行解析vectorintanswer(n,1);初始化结果数组所有元素设为 11 是乘法的单位元不影响结果intleft1;for(inti0;in;i){answer[i]left;left*nums[i];}left代表索引 i 左侧所有元素的乘积第一次循环answer[0] 1左侧无元素left 1第二次循环answer[1] 1左侧只有 nums[0]left 1*2 2以此类推intright1;for(intin-1;i0;i--){answer[i]*right;right*nums[i];}right代表索引 i 右侧所有元素的乘积从右向左遍历乘上右侧的累乘第一次循环answer[3] * 1右侧无元素right 4第二次循环answer[2] 4right 43 12以此类推五、为什么不能用除法如果使用除法 total nums[0] * nums[1] * ... * nums[n-1] answer[i] total / nums[i] 问题 1. 题目明确禁止使用除法 2. 如果 nums[i] 0无法除法 3. 整数除法可能有精度问题 因此必须用左右乘积法。六、与第 238 题的相似题目对比题目难度核心差异238. 除自身以外数组的乘积中等左右乘积O(1) 空间42. 接雨水困难左右高度O(1) 空间11. 盛水最多的容器中等双指针左右夹击152. 乘积最大子数组中等需要处理负数七、复杂度分析方法时间复杂度空间复杂度备注左右乘积法O(n)O(1)推荐输出数组不算额外空间前缀后缀数组O(n)O(n)空间不优除法禁止O(n)O(1)题目禁止详细分析时间复杂度 第一步遍历O(n) 第二步遍历O(n) 总计O(2n) O(n) 空间复杂度 输出数组 answer 不算额外空间 只使用 left, right 两个变量O(1)八、边界情况分析情况处理方式有零元素左侧乘积 × 右侧乘积 0答案正确多个零所有位置答案都是 0无法利用任何非零元素全是正数正常处理有负数正常处理乘积正负取决于负数个数全是 1answer 全是 n-1 个 1 的乘积 1示例有零元素的情况nums [-1, 1, 0, -3, 3] answer[0] 1 * 1 * 0 * -3 * 3 0 answer[1] -1 * 1 * 0 * -3 * 3 0 answer[2] -1 * 1 * 0 * -3 * 3 0 (除了自身都是0) answer[3] -1 * 1 * 0 * 3 0 answer[4] -1 * 1 * 0 * -3 0 结果: [0, 0, 9, 0, 0] (注意 answer[2] 9因为左右两侧都没有0)九、面试追问 FAQ问题回答要点Q: 为什么输出数组不算额外空间输出数组是题目要求返回的结果不是额外申请的辅助空间Q: 为什么两次遍历不能合并成一次第一步需要从左到右计算前缀第二步需要从右到左计算后缀方向不同无法合并Q: 如何处理 nums[i] 0 的情况不需要特殊处理左右乘积法自动给出正确答案Q: 时间复杂度能否小于 O(n)不能至少需要遍历一次数组读取所有元素Q: 空间复杂度能否到 O(1)可以左右乘积法只需要两个变量Q: 能否用递归递归虽然可以用栈空间但会引入 O(n) 栈空间不推荐十、相关题目题目编号题目名称难度核心差异238除自身以外数组的乘积中等基础题左右乘积42接雨水困难双指针左右夹击152乘积最大子数组中等需要处理负数情况628三个数的最大乘积简单先排序再计算134加油站中等环形遍历485最大连续 1 的个数简单单次遍历十一、总结要点内容核心思想answer[i] 左侧乘积 × 右侧乘积算法两遍遍历第一遍左到右第二遍右到左禁止不能使用除法时间复杂度O(n)空间复杂度O(1)输出数组不算关键变量left左累乘、right右累乘特点充分利用前缀和后缀的对称性除自身以外数组的乘积是经典的左右乘积问题核心思想是利用前缀和后缀的对称性O(1) 空间内完成 O(n) 的计算。