双因子前缀和与二分查找优雅解决乘积尾随零问题在算法竞赛和编程面试中我们经常会遇到需要统计满足特定条件的子区间数量的问题。这类问题看似简单但如果采用暴力枚举的方法时间复杂度往往难以接受。本文将以乘积尾随零这一经典问题为例介绍如何利用双因子前缀和与二分查找的组合技巧将时间复杂度从O(n²)优化到O(nlogn)。1. 问题本质与数学建模乘积尾随零的数量由乘数中2和5因子的最小值决定。例如数字20可以分解为2²×5¹因此贡献2个2因子和1个5因子。整个数组乘积的尾随零数量等于所有元素中2因子总数和5因子总数的较小值。关键数学转化设原数组总2因子数为total2总5因子数为total5删除区间中的2因子数为x25因子数为x5剩余部分需要满足min(total2-x2, total5-x5) ≥ k这等价于两个独立不等式x2 ≤ total2-k 且 x5 ≤ total5-kdef count_factors(num, factor): count 0 while num % factor 0 and num ! 0: count 1 num // factor return count2. 暴力解法的局限性最直观的方法是枚举所有可能的删除区间然后检查是否满足条件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) res 0 for i in range(n): curr2 curr5 0 for j in range(i, n): curr2 factor2[j] curr5 factor5[j] if curr2 total2 - k and curr5 total5 - k: res 1 else: break return res这种方法的时间复杂度为O(n²)当n1e5时完全无法接受。我们需要更高效的解决方案。3. 前缀和与二分查找的优雅结合3.1 前缀和预处理首先我们计算2因子和5因子的前缀和数组from itertools import accumulate from bisect import bisect_right def preprocess(nums): factor2 [count_factors(num, 2) for num in nums] factor5 [count_factors(num, 5) for num in nums] prefix2 [0] list(accumulate(factor2)) prefix5 [0] list(accumulate(factor5)) return prefix2, prefix53.2 双约束条件的转化对于每个左端点i我们需要找到最大的j使得prefix2[j] - prefix2[i] ≤ total2 - kprefix5[j] - prefix5[i] ≤ total5 - k这可以转化为prefix2[j] ≤ prefix2[i] (total2 - k)prefix5[j] ≤ prefix5[i] (total5 - k)3.3 二分查找确定边界使用bisect_right可以高效找到满足条件的最大jdef solve(nums, k): prefix2, prefix5 preprocess(nums) total2, total5 prefix2[-1], prefix5[-1] n len(nums) res 0 for i in range(n1): max2 prefix2[i] (total2 - k) max5 prefix5[i] (total5 - k) j2 bisect_right(prefix2, max2) - 1 j5 bisect_right(prefix5, max5) - 1 valid_j min(j2, j5) if valid_j i: res valid_j - i return res4. 算法复杂度分析时间复杂度预处理阶段O(n)计算因子数量O(n)构建前缀和数组查询阶段n次二分查找每次O(logn)总复杂度O(nlogn)空间复杂度需要存储两个前缀和数组O(n)5. 模式扩展与应用这种双因子前缀和二分查找的技术可以推广到多种类似问题双约束子区间计数任何需要同时满足两个独立条件的子区间统计问题多因子扩展如果问题需要考虑更多质因子方法依然适用其他运算将乘积替换为加法、异或等运算只要满足前缀和性质对比表格方法时间复杂度适用场景实现难度暴力枚举O(n²)小规模数据简单滑动窗口O(n)单约束条件中等前缀和二分O(nlogn)多约束条件较高6. 实战技巧与优化建议预处理优化可以并行计算2和5因子减少循环次数边界处理特别注意前缀和数组的初始0值二分查找选择bisect_right返回第一个大于目标的位置bisect_left返回第一个大于等于目标的位置提前终止如果total2或total5小于k直接返回0# 优化后的完整解法 def optimized_solution(nums, k): n len(nums) # 并行计算因子 factor2 [0]*n factor5 [0]*n for i in range(n): num nums[i] while num % 2 0 and num ! 0: factor2[i] 1 num // 2 while num % 5 0 and num ! 0: factor5[i] 1 num // 5 # 计算前缀和 prefix2 [0]*(n1) prefix5 [0]*(n1) for i in range(n): prefix2[i1] prefix2[i] factor2[i] prefix5[i1] prefix5[i] factor5[i] total2, total5 prefix2[-1], prefix5[-1] if min(total2, total5) k: return 0 res 0 for i in range(n1): max2 prefix2[i] (total2 - k) max5 prefix5[i] (total5 - k) j2 bisect_right(prefix2, max2) - 1 j5 bisect_right(prefix5, max5) - 1 valid_j min(j2, j5) if valid_j i: res valid_j - i return res7. 常见错误与调试技巧边界条件处理不当忘记前缀和数组的初始0没有处理total2或total5小于k的情况二分查找使用错误混淆bisect_left和bisect_right忘记调整返回的索引因子计算错误没有处理num为0的情况因子计数循环条件错误调试建议先用小规模数据验证打印中间变量检查对比暴力解法的结果
别再暴力枚举了！用‘双因子前缀和+二分’优雅解决LeetCode风格问题：以乘积尾随零为例
发布时间：2026/6/2 3:53:36
双因子前缀和与二分查找优雅解决乘积尾随零问题在算法竞赛和编程面试中我们经常会遇到需要统计满足特定条件的子区间数量的问题。这类问题看似简单但如果采用暴力枚举的方法时间复杂度往往难以接受。本文将以乘积尾随零这一经典问题为例介绍如何利用双因子前缀和与二分查找的组合技巧将时间复杂度从O(n²)优化到O(nlogn)。1. 问题本质与数学建模乘积尾随零的数量由乘数中2和5因子的最小值决定。例如数字20可以分解为2²×5¹因此贡献2个2因子和1个5因子。整个数组乘积的尾随零数量等于所有元素中2因子总数和5因子总数的较小值。关键数学转化设原数组总2因子数为total2总5因子数为total5删除区间中的2因子数为x25因子数为x5剩余部分需要满足min(total2-x2, total5-x5) ≥ k这等价于两个独立不等式x2 ≤ total2-k 且 x5 ≤ total5-kdef count_factors(num, factor): count 0 while num % factor 0 and num ! 0: count 1 num // factor return count2. 暴力解法的局限性最直观的方法是枚举所有可能的删除区间然后检查是否满足条件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) res 0 for i in range(n): curr2 curr5 0 for j in range(i, n): curr2 factor2[j] curr5 factor5[j] if curr2 total2 - k and curr5 total5 - k: res 1 else: break return res这种方法的时间复杂度为O(n²)当n1e5时完全无法接受。我们需要更高效的解决方案。3. 前缀和与二分查找的优雅结合3.1 前缀和预处理首先我们计算2因子和5因子的前缀和数组from itertools import accumulate from bisect import bisect_right def preprocess(nums): factor2 [count_factors(num, 2) for num in nums] factor5 [count_factors(num, 5) for num in nums] prefix2 [0] list(accumulate(factor2)) prefix5 [0] list(accumulate(factor5)) return prefix2, prefix53.2 双约束条件的转化对于每个左端点i我们需要找到最大的j使得prefix2[j] - prefix2[i] ≤ total2 - kprefix5[j] - prefix5[i] ≤ total5 - k这可以转化为prefix2[j] ≤ prefix2[i] (total2 - k)prefix5[j] ≤ prefix5[i] (total5 - k)3.3 二分查找确定边界使用bisect_right可以高效找到满足条件的最大jdef solve(nums, k): prefix2, prefix5 preprocess(nums) total2, total5 prefix2[-1], prefix5[-1] n len(nums) res 0 for i in range(n1): max2 prefix2[i] (total2 - k) max5 prefix5[i] (total5 - k) j2 bisect_right(prefix2, max2) - 1 j5 bisect_right(prefix5, max5) - 1 valid_j min(j2, j5) if valid_j i: res valid_j - i return res4. 算法复杂度分析时间复杂度预处理阶段O(n)计算因子数量O(n)构建前缀和数组查询阶段n次二分查找每次O(logn)总复杂度O(nlogn)空间复杂度需要存储两个前缀和数组O(n)5. 模式扩展与应用这种双因子前缀和二分查找的技术可以推广到多种类似问题双约束子区间计数任何需要同时满足两个独立条件的子区间统计问题多因子扩展如果问题需要考虑更多质因子方法依然适用其他运算将乘积替换为加法、异或等运算只要满足前缀和性质对比表格方法时间复杂度适用场景实现难度暴力枚举O(n²)小规模数据简单滑动窗口O(n)单约束条件中等前缀和二分O(nlogn)多约束条件较高6. 实战技巧与优化建议预处理优化可以并行计算2和5因子减少循环次数边界处理特别注意前缀和数组的初始0值二分查找选择bisect_right返回第一个大于目标的位置bisect_left返回第一个大于等于目标的位置提前终止如果total2或total5小于k直接返回0# 优化后的完整解法 def optimized_solution(nums, k): n len(nums) # 并行计算因子 factor2 [0]*n factor5 [0]*n for i in range(n): num nums[i] while num % 2 0 and num ! 0: factor2[i] 1 num // 2 while num % 5 0 and num ! 0: factor5[i] 1 num // 5 # 计算前缀和 prefix2 [0]*(n1) prefix5 [0]*(n1) for i in range(n): prefix2[i1] prefix2[i] factor2[i] prefix5[i1] prefix5[i] factor5[i] total2, total5 prefix2[-1], prefix5[-1] if min(total2, total5) k: return 0 res 0 for i in range(n1): max2 prefix2[i] (total2 - k) max5 prefix5[i] (total5 - k) j2 bisect_right(prefix2, max2) - 1 j5 bisect_right(prefix5, max5) - 1 valid_j min(j2, j5) if valid_j i: res valid_j - i return res7. 常见错误与调试技巧边界条件处理不当忘记前缀和数组的初始0没有处理total2或total5小于k的情况二分查找使用错误混淆bisect_left和bisect_right忘记调整返回的索引因子计算错误没有处理num为0的情况因子计数循环条件错误调试建议先用小规模数据验证打印中间变量检查对比暴力解法的结果
