从美团春招真题‘区间删除’出发，聊聊如何用Python前缀和+二分搞定乘积末尾零问题

从美团春招真题看乘积末尾零问题前缀和与二分的Python实战在算法面试中大厂常常会考察候选人对数学问题的算法转化能力。美团春招中的这道区间删除题目表面上是一个数组操作问题实则考察了乘积末尾零的数学本质与高效算法的结合。本文将带您深入剖析这个问题从暴力解法到优化方案最后给出一个时间复杂度为O(nlogn)的优雅解决方案。1. 问题本质与数学建模乘积末尾零的数量由什么决定这是一个看似简单却容易忽略本质的问题。实际上末尾零的数量取决于乘数中2和5因子数量的较小值。例如10 2×5 → 1个零100 2²×5² → 2个零8×125 2³×5³ → 3个零对于给定的数组我们需要计算每个元素的2因子和5因子数量def count_factors(n, factor): count 0 while n 0 and n % factor 0: count 1 n // factor return count原始问题转化为删除一个区间后剩余元素的2因子总数和5因子总数的较小值至少为k。设总2因子为total2总5因子为total5删除区间的2、5因子分别为x2和x5则需要满足min(total2 - x2, total5 - x5) k这等价于两个不等式x2 total2 - k x5 total5 - k2. 暴力解法及其局限性最直观的方法是检查所有可能的删除区间def brute_force(nums, k): n len(nums) factor2 [count_factors(num, 2) for num in nums] factor5 [count_factors(num, 5) for num in nums] total2, total5 sum(factor2), sum(factor5) count 0 for i in range(n): x2 x5 0 for j in range(i, n): x2 factor2[j] x5 factor5[j] if x2 total2 - k and x5 total5 - k: count 1 else: break return count这种方法的时间复杂度为O(n²)对于n1e5的数据规模显然无法接受。我们需要更高效的算法。3. 前缀和与二分查找优化前缀和数组可以快速计算任意区间的因子和。对于2因子和5因子我们分别构建前缀和数组from itertools import accumulate from bisect import bisect_right def optimized_solution(nums, k): n len(nums) factor2 [count_factors(num, 2) for num in nums] factor5 [count_factors(num, 5) for num in nums] total2, total5 sum(factor2), sum(factor5) prefix2 [0] list(accumulate(factor2)) prefix5 [0] list(accumulate(factor5)) count 0 for i in range(n 1): max_x2 total2 - k max_x5 total5 - k # 对于当前i找到最大的j满足prefix2[j] - prefix2[i] max_x2 # 即 prefix2[j] prefix2[i] max_x2 j2 bisect_right(prefix2, prefix2[i] max_x2) - 1 j5 bisect_right(prefix5, prefix5[i] max_x5) - 1 # 取较小的j作为有效右边界 valid_j min(j2, j5) if valid_j i: count valid_j - i return count这个算法的时间复杂度为O(nlogn)主要来自二分查找操作。对于每个左端点i我们使用二分查找确定满足条件的最大右端点j。4. 算法正确性验证与边界处理让我们用题目中的示例验证算法正确性输入n5, k2 nums [2, 5, 3, 4, 20]计算各数的因子数量数字2因子5因子2105013004202021总和total25, total52需要满足x2 5-23 x5 2-20即删除区间内的5因子总和必须为0因为total5-k0且2因子总和不超过3。符合条件的删除区间有[3] (无5因子2因子0)[4] (无5因子2因子2)[3,4] (无5因子2因子2)[2] (无5因子2因子1)与题目给出的示例输出一致验证了算法的正确性。5. 性能对比与面试技巧在实际面试中展示从暴力解法到优化解法的思考过程非常重要。下表对比了两种方法的性能方法时间复杂度空间复杂度适用数据规模暴力枚举O(n²)O(n)n 1e4前缀和二分查找O(nlogn)O(n)n ≤ 1e6面试中建议的解题步骤明确问题本质乘积末尾零的数学原理提出暴力解法并分析复杂度寻找优化点前缀和快速查询区间和应用二分查找减少枚举次数处理边界条件和验证正确性6. 代码实现细节与调试技巧完整实现需要考虑几个关键点因子计数函数的边界处理0和1的情况前缀和数组的构建通常会在前面加0方便计算二分查找的边界条件调试时可以打印中间变量print(Factor 2 counts:, factor2) print(Factor 5 counts:, factor5) print(Prefix2:, prefix2) print(Prefix5:, prefix5)对于二分查找不确定的情况可以单独测试# 测试bisect_right的行为 arr [1, 3, 5, 7] print(bisect_right(arr, 4)) # 输出2因为4应该插入在3和5之间7. 同类问题扩展与举一反三掌握这个问题的解法后可以解决一系列类似问题子数组乘积末尾零的最大数量找所有子数组中min(sum2, sum5)的最大值必须包含某元素的子数组乘积末尾零数量固定左或右端点多维度的约束条件如同时满足sum2≥a且sum5≥b的子数组数量以第一个扩展问题为例解法框架类似def max_trailing_zeros(nums): factor2 [count_factors(num, 2) for num in nums] factor5 [count_factors(num, 5) for num in nums] max_zeros 0 current2 current5 0 for num2, num5 in zip(factor2, factor5): current2 num2 current5 num5 max_zeros max(max_zeros, min(current2, current5)) # 可选的滑动窗口优化 return max_zeros8. 面试中的常见误区与避坑指南在解决此类问题时候选人常犯以下错误误解末尾零的产生机制只考虑5因子而忽略2因子错误计算因子数量特别是对于大数和0的处理优化思路不清晰直接从暴力跳到最优解缺乏中间思考过程边界条件处理不当如空数组、全1数组、包含0的数组特别要注意0的情况——任何包含0的数组乘积都是0理论上可以有无限多个末尾零实际处理时可能需要特殊判断。