hot100 除了自身以外数组的乘积(238)

📅 2026/7/1 15:17:20 👁️ 次浏览

本题采用前缀与后缀乘积空间复用算法解决“除自身以外数组的乘积”问题。其核心本质是在禁用除法的前提下利用输出数组直接存储前缀连续乘积并引入单个滚动变量逆向累乘后缀从而将传统多数组方案的额外空间复杂度由 O(n) 降低至 O(1)。该解法实现了时间与额外空间的双重理论极限最终走向是通过两次完备的线性扫描直接锁定目标乘积序列。一、问题本质与数据模型对于长度为 n 的整数数组 nums设任意位置 i其中 0 i n的目标乘积为 answer[i]。根据题目定义answer[i] 等于该位置左侧所有元素的乘积前缀乘积与右侧所有元素的乘积后缀乘积的乘积。物理模型可拆解为Prefix[i] nums[0] * nums[1] * ... * nums[i-1] 约定 Prefix[0] 1Suffix[i] nums[i1] * nums[i2] * ... * nums[n-1] 约定 Suffix[n-1] 1answer[i] Prefix[i] * Suffix[i]传统方案需要分别开辟两个独立的空间为 O(n) 的辅助数组来存储 Prefix 和 Suffix。而本算法通过重用输出数组并配合动态变量彻底消除了额外辅助数组的开销。二、算法演进对比在处理区间全量乘积去中心化问题时空间复用双向扫描法达成了资源配置的最优解解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷除法扫描法O(n)O(1)先计算全局总乘积遍历时除以当前元素得到结果无法处理数组中包含元素 0 的特殊情况且违反题目禁用除法的物理约束暴力双重循环O(n^2)O(1)每到一个位置线性遍历其余 n-1 个元素并求乘积存在大量重叠区间的重复计算大数级样本下必然超时双辅助数组法O(n)O(n)开辟 PREFIX 和 SUFFIX 数组分别向前和向后累乘后进行对应相乘引入了两倍于输入规模的额外内存开销空间复用扫描当前解法O(n)O(1)利用返回数组替代 PREFIX 数组利用动态单变量滚动代替 SUFFIX 数组需进行正反两次完备的线性扫描三; 核心控制流逻辑推导提供的源码通过解耦前缀和后缀的计算分两步完成了对输出数组ans的构建1. 正向扫描构建前缀乘积控制循环for (int i 1; i nums.length; i)初始边界设定ans[0] 1。因为索引 0 左侧没有元素前缀乘积默认为 1。状态转移ans[i] ans[i - 1] * nums[i - 1]逻辑证明此时ans[i]严格等于nums[0]到nums[i-1]的连续累乘。当这轮循环结束时ans数组中已经保存了所有元素对应的完整前缀乘积。2. 逆向扫描融合后缀乘积控制循环for (int i nums.length - 1; i 0; i--)引入滚动变量r初始值为 1代表当前位置右侧所有元素的累乘和即后缀乘积。复合更新ans[i] * r此时ans[i]的值变为原有的前缀乘积 * 当前的后缀乘积 r直接完成了answer[i]的最终物理赋值。动态演进r * nums[i]更新后r融入了当前的nums[i]为左边下一个位置i-1的后缀乘积做好了数据准备。四、算法执行状态机步进示例以输入数据nums [1, 2, 3, 4]为例算法内部各变量与ans数组的动态演进过程如下表所示阶段 / 步骤当前指针 i当前元素 nums[i]滚动变量 r 的值ans 数组实时状态物理意义说明初始化---[1, 0, 0, 0]设定首位前缀初始值正向第 1 步12-[1, 1, 0, 0]ans[1] ans[0] * nums[0] 1 * 1正向第 2 步23-[1, 1, 2, 0]ans[2] ans[1] * nums[1] 1 * 2正向第 3 步34-[1, 1, 2, 6]ans[3] ans[2] * nums[2] 2 * 3 (正向结束)逆向第 1 步341[1, 1, 2, 6]ans[3] * 1 - 6; r 更新为 1 * 4 4逆向第 2 步234[1, 1, 8, 6]ans[2] * 4 - 8; r 更新为 4 * 3 12逆向第 3 步1212[1, 12, 8, 6]ans[1] * 12 - 12; r 更新为 12 * 2 24逆向第 4 步0124[24, 12, 8, 6]ans[0] * 24 - 24; r 更新为 24 * 1 24五、源码实现class Solution { public int[] productExceptSelf(int[] nums) { // 创建结果数组根据空间复杂度分析原则该数组不计入额外空间开销 int[] ans new int[nums.length]; // 边界初始化第一个元素左边没有元素前缀乘积设定为 1 ans[0] 1; // 步骤 1正向遍历计算每个元素的所有前缀乘积 for (int i 1; i nums.length; i) { ans[i] ans[i - 1] * nums[i - 1]; } // 动态滚动变量 r用来实时维护当前元素右侧所有元素的连续乘积后缀乘积 int r 1; // 步骤 2逆向遍历将前缀乘积与动态生成的后缀乘积进行融合 for (int i nums.length - 1; i 0; i--) { // 当前位置的最终结果已经存在数组中的前缀乘积 * 当前右侧的后缀乘积 ans[i] * r; // 滚动变量更新将当前元素纳入后缀乘积供左侧的下一个元素使用 r * nums[i]; } return ans; } }六、复杂度极限分析1. 时间复杂度O(n)分析算法包含两个独立的、不嵌套的单层for循环。第一个循环从前往后遍历长度为 n 的数组执行次数为 n-1 次第二个循环从后往前逆序遍历数组执行次数为 n 次。两轮遍历中的基础操作均为单次的常数阶乘法运算O(1)。结论总体总基本操作次数与输入数据规模 n 呈线性正比关系时间复杂度为稳定的 O(n)。2. 空间复杂度O(1)分析根据题目设定的空间复杂度分析原则输出数组ans作为返回值不被计入额外的物理空间开销。在算法执行期间除返回值外仅独立申请了一个基础类型的整型滚动变量r以及循环控制变量i。结论算法所额外分配的物理内存空间完全恒定不随输入规模 n 的扩大而产生任何增长空间复杂度达到了 O(1) 阶的极限原地状态。

相关新闻