【Hot 100 刷题计划】 LeetCode 238. 除自身以外数组的乘积 | C++ 前后缀分解题解

LeetCode 238. 除自身以外数组的乘积 | C 前后缀分解与 O(1) 空间优化 题目描述题目级别中等给你一个整数数组nums返回数组answer其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积。题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。请不要使用除法且在O(N)O(N)O(N)时间复杂度内完成此题。示例 1:输入:nums [1,2,3,4]输出:[24,12,8,6] 解题思路前后缀分解题目严禁使用除法否则直接求总乘积再除以当前元素即可还要考虑 0 的特判非常麻烦。既然不能用除法我们可以换个视角“除自身以外的乘积”是不是就等于“它左边所有数字的乘积”×\timesד它右边所有数字的乘积” 解法一双数组记录前后缀 (思路直观空间 O(N))我们可以开辟两个数组L数组L[i]记录索引i左侧所有元素的乘积。R数组R[i]记录索引i右侧所有元素的乘积。最后遍历一次answer[i] L[i] * R[i]即可。 C 代码实现 (标准规范版)classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();// 使用 vector 代替变长数组 (VLA)符合 C 标准规范vectorintL(n,1);vectorintR(n,1);vectorintres(n);// 1. 计算左侧所有元素的乘积// L[0] 默认为 1因为索引 0 左侧没有元素for(inti1;in;i){L[i]L[i-1]*nums[i-1];}// 2. 计算右侧所有元素的乘积// R[n-1] 默认为 1因为最后一个元素右侧没有元素for(intin-2;i0;i--){R[i]R[i1]*nums[i1];}// 3. 计算最终结果左侧乘积 * 右侧乘积for(inti0;in;i){res[i]L[i]*R[i];}returnres;}}; 解法二巧妙利用结果数组 (空间 O(1) 面试终极解)面试官的终极追问“输出数组不计入空间复杂度你能只用O(1)O(1)O(1)的额外空间做出来吗”核心优化思想动态计算就地利用既然题目允许我们返回一个结果数组res我们完全可以把res当作解法一中的L数组来用第一遍从左到右我们直接把前缀乘积计算好存进res里。此时res[i]里装的就是左侧元素的乘积。第二遍从右到左我们不再需要额外的R数组了。我们只需要用一个单独的整型变量R_{mult}来实时记录右侧的累计乘积。边走边乘res[i] res[i] * R_{mult}然后更新R_{mult} R_{mult} * nums[i]。这样完美省去了两个O(N)O(N)O(N)数组的开销 进阶 C 代码实现classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();vectorintres(n,1);// 第一遍从左到右res[i] 暂时用来存储左侧所有元素的乘积intL_mult1;for(inti0;in;i){res[i]L_mult;L_mult*nums[i];// 更新前缀乘积}// 第二遍从右到左用一个变量 R_mult 动态追踪右侧元素的乘积intR_mult1;for(intin-1;i0;i--){// 当前位置的最终结果 已经存好的左侧乘积 (res[i]) * 刚刚算好的右侧乘积 (R_mult)res[i]*R_mult;// 更新后缀乘积供下一个左边的元素使用R_mult*nums[i];}returnres;}};