昨天整理基础算法题库时又碰到了这道“在区间范围内统计奇数数目”。题目本身很简单给定两个非负整数 low 和 high返回区间 [low, high] 内所有奇数的数目。很多刚刷题的朋友第一反应是写个 for 循环判断每个数是否为奇数然后计数。这个做法当然能过测试用例但一旦区间规模拉满到 10^9 级别循环解法就会暴露性能问题。这篇文章就从暴力解讲起逐步引出 O(1) 的数学解法并重点讲清楚边界条件和公式推导中容易踩的坑适合正在准备面试算法题、刚入门刷题、或者想系统梳理基础数学技巧的同学参考。1. 暴力解法为什么不够用从循环计数到性能瓶颈先看大多数人最容易想到的写法。遍历区间里的每个整数用x % 2 ! 0判断是否为奇数是则计数器加一。伪代码大概长这样int countOdds(int low, int high) { int count 0; for (int i low; i high; i) { if (i % 2 ! 0) count; } return count; }这段代码逻辑上没有毛病对于小范围区间比如[3, 7]运行结果完全正确。但它的问题在于时间复杂度是 O(n)n 是区间长度high - low 1。当区间跨度达到几千万甚至上亿时循环体内每一次取模运算和比较操作都会被放大到不可接受的程度。我在实际测试中发现当区间长度在 10^6 量级时暴力解还能在两三毫秒内跑完一旦区间长度变成 10^8 甚至 2^31也就是题目允许的极限范围循环解法的耗时就会飙升到数百毫秒甚至秒级这在严格限时的评测环境里基本就超时了。1.1 奇数判断的本质对 2 取模的背后逻辑这里值得多说一句“为什么x % 2 ! 0能判断奇数”。整数对 2 取模余数只有 0 和 1 两种可能。余 0 意味着这个数可以被 2 整除是偶数余 1 则意味着它比某个偶数多 1是奇数。这是整数除法的基本性质也是奇偶性判断最直观的数学依据。在面试中有些候选人会写x % 2 1来判断奇数这在多数主流语言里没问题但在某些语言处理负数时会踩坑。比如 JavaScript 和 Python 里-3 % 2的结果是 1Python 取余结果符号跟随除数可如果面试官用的是另一种规则-3 % 2可能得到 -1此时 1的判断就会漏掉奇数。所以更稳妥的做法是判断x % 2 ! 0或者直接对 2 取绝对值的余数。这道题的输入虽然限定了非负整数但写出更健壮的判断习惯终归是好的。1.2 为什么说“小学数学”能在算法题里救命当区间很大时暴力循环不可行这时候就需要从数学规律入手。奇数和偶数在数轴上是交替出现的0, 1, 2, 3, 4, 5, 6, 7……可以看到每两个连续整数里恰好有一个奇数、一个偶数。这个“二选一”的周期规律是所有 O(1) 解法的根基。换句话说如果我们知道从 0 到某个数 n 之间有多少个奇数那么任意区间的奇数个数就可以通过前缀和的方式做减法求得。这就像我们用总金额减去已花金额得到剩余金额一样把一个包含边界的问题拆成两个前缀区间的差。这个“前缀差”的思路在算法题里非常常见后面推导公式时你还会看到它的身影。2. O(1) 数学解法的推导过程从前缀函数到区间减法既然暴力解在大区间下不可行那就需要设计一个与区间长度无关的计算方法。我先把问题拆成两部分定义函数oddCount(n)表示区间[0, n]内奇数的个数那么题目要求的[low, high]内奇数个数就等于oddCount(high) - oddCount(low - 1)。为什么是low - 1而不是low因为oddCount(low)会把low本身也包含进去如果low恰好是奇数不减掉就会多算一个所以必须用low - 1把左边界排除在外。2.1 一对一地数oddCount(n)的通项公式接着推导oddCount(n)。从 0 到 n 一共有n 1个整数注意这里要加 1因为区间包含两个端点。奇数在这些整数里的分布是每隔一个出现一次所以奇数的个数正好是这“n 1 个数里有多少个完整的‘一对儿’”余下的部分再判断是否为奇数。更严谨的说法是前n 1个数可以每两个一组。如果n 1是偶数那么奇数个数就是(n 1) / 2如果n 1是奇数那么前n个数里正好有n / 2个奇数而最后一个数n本身如果是奇数则再加 1。合并这两种情况就能得到通式oddCount(n) (n 1) / 2 整数除法向下取整让我举个具体例子验证。n 5时从 0 到 5 的数有 0, 1, 2, 3, 4, 5其中奇数是 1, 3, 5共 3 个。套公式(5 1) / 2 3正确。n 6时区间[0, 6]的奇数是 1, 3, 5也是 3 个套公式(6 1) / 2 3整数除法 7/2 向下取整为 3同样正确。这个通式在任何非负整数 n 下都成立。2.2 套用前缀差区间减法公式的最终形态回到原题。把oddCount(high) - oddCount(low - 1)展开就得到countOdds(low, high) (high 1) / 2 - low / 2注意这里第二项是low / 2整数除法而不是(low - 1 1) / 2再化简——其实两者是等价的。因为oddCount(low - 1) ((low - 1) 1) / 2 low / 2所以公式写为(high 1) / 2 - low / 2完全正确。这在数学上化简后其实也可以写成(high - low) / 2再加一个常数修正但直接使用前者更不容易出错。验证一组数据low 3, high 7区间内奇数为 3, 5, 7共 3 个。套公式(7 1) / 2 - 3 / 2 4 - 1 3正确。再看low 2, high 2区间只有一个偶数 2奇数个数应为 0。套公式(2 1) / 2 - 2 / 2 1 - 1 0正确。再看low 1, high 1区间只有奇数 1结果应为 1。套公式(1 1) / 2 - 1 / 2 1 - 0 1正确。2.3 另一种等价形态(high / 2) - (low - 1) / 2的推导除了上面这个公式还有另一种常见写法high / 2 - (low - 1) / 2这里的高低位都用整数除法。让我解释一下它是怎么来的oddCount(n)其实也可以直接用n / 2再加修正看待因为从 0 到 n 的奇数个数等于“n 以内有多少个偶数对儿”的变体。但为了少记一个公式我更推荐只记一个先定义oddCount(n) (n 1) / 2然后用前缀差。这样不管题目怎么变你只要会求前缀区间的奇数个数就能应对。我平时刷题时习惯把这类公式记在脑子里但真正面试时更推荐当场推导一遍因为面试官往往更看重你“为什么这么做”的思考过程而不是直接背答案。下面的可视化章节会从另一个角度帮你建立直觉。3. 公式可视化验证与边界情形用具体数字建立直觉数学公式推导完毕但为了让直觉更扎实我建议你亲手在纸上列几个区间把暴力解和公式解的结果对齐一遍。下面这张表格覆盖了常见的边界情况我每次讲这道题时都会拿它来做验证。区间实际奇数列表暴力解公式解(high1)/2 - low/2结果是否一致[0, 0]无0(01)/2 - 0/2 0 - 0 0一致[0, 1]11(11)/2 - 0/2 1 - 0 1一致[1, 1]11(11)/2 - 1/2 1 - 0 1一致[1, 2]11(21)/2 - 1/2 1 - 0 1一致[2, 2]无0(21)/2 - 2/2 1 - 1 0一致[2, 5]3, 52(51)/2 - 2/2 3 - 1 2一致[3, 7]3, 5, 73(71)/2 - 3/2 4 - 1 3一致[0, 100]1,3,...,9950(1001)/2 - 0/2 50 - 0 50一致[99, 100]991(1001)/2 - 99/2 50 - 49 1一致3.1 偶数起点与奇数起点公式为什么能“自动处理”起点奇偶不少人第一次看到公式时会有疑问如果low是奇数减法会不会把low本身漏掉答案是不会。因为公式里的第二项用的是low / 2而不是(low 1) / 2它只减去了区间[0, low-1]内的奇数个数。举个例子low 3时3 / 2 1正好对应[0, 2]内的奇数 1 这一个并没有把 3 本身算进去。于是oddCount(high)里的奇数列表包含了 3减去的部分又不包含 3一加一减就把 3 保留了下来。如果low是偶数比如low 4那么4 / 2 2对应[0, 3]内的奇数 1 和 3 这两个同样不包含 44 本身是偶数本来也不在奇数列表里。所以无论起点奇偶公式都能精确算出区间内的奇数个数。这种“边界自动修正”的特性正是前缀差公式的魅力所在。3.2 从奇数映射到等差数列的角度再理解一遍换个视角来看这个问题区间[low, high]里的奇数本质上是一个首项为low如果low是奇数或low1如果low是偶数、公差为 2 的等差数列。最后一项不超过high。这个数列的项数就是题目答案。等差数列求项数的公式是(末项 - 首项) / 公差 1所以你也可以先判断首项、末项的奇偶再代入公式。但这样做需要处理四种组合分类讨论比较繁琐。相比之下前缀差公式只需要两次整数除法和一次减法简洁得多。我在面试中更喜欢用前缀差因为它不需要在脑子里做奇偶分支判断代码写出来也短。4. 代码实现的细节与语言差异溢出、整除方向与可读性公式理清楚之后代码实现基本就是照抄。但不同语言的整数除法规则略有差异尤其是负数场景下可能产生误导所以这里单独列一节讲编码细节。4.1 主流语言的参考实现Python 实现def count_odds(low: int, high: int) - int: return (high 1) // 2 - low // 2Python 的//是向下取整除法对于非负整数来说等价于整数除法。因为题目限定了非负整数所以写起来最干净。C 实现int countOdds(int low, int high) { return (high 1) / 2 - low / 2; }Java 实现class Solution { public int countOdds(int low, int high) { return (high 1) / 2 - low / 2; } }4.2 大数场景下的溢出陷阱high 1到底要不要担心在大多数在线评测系统里low和high被限定为0 low high 10^9用 32 位整数完全装得下。但如果你把范围拉满到2^31 - 1附近high 1就可能超过int的最大值2^31 - 1造成整数溢出。我在本地测试时确实遇到过这个问题。比如low 0, high 2147483647即2^31 - 1在 Java 里直接算(high 1) / 2high 1会溢出成负数结果变成负数再除整个答案就错了。解决办法很简单要么把high转成long要么用high / 2 1之类的方式避免先加后除。推荐一个更安全的写法以 Java 为例class Solution { public int countOdds(int low, int high) { long h high; long l low; return (int)((h 1) / 2 - l / 2); } }或者干脆用(high - low 1 (low 1)) / 2等变体这取决于你更喜欢哪种表达。但无论如何做算法题时一定要留意中间运算的溢出风险这往往是提交才会暴露的隐藏雷区。4.3 边界场景的测试用例设计列一份自查清单写完代码后我建议至少跑这样一组测试数据能够一次性覆盖最容易出错的边界low 0, high 0答案 0low 0, high 1答案 1low 1, high 1答案 1low 1, high 2答案 1low 2, high 2答案 0low 0, high 1000000000答案 500000000low 2147483646, high 2147483647答案 1同时测试溢出情况。我最初写这道题时就是在low 1, high 2这种情况上犯过糊涂一度以为答案是 2后来才意识到区间 [1,2] 只有 1 和 2 两个数奇数只有一个。这种低级错误靠一张手工验算表就能避免。5. 从一个公式到一类问题区间内任意整除数的通解统计奇数本质上是在统计“能被 2 整除余 1”的数。如果把 2 换成任意正整数k就变成了一道更一般的题统计区间[low, high]内能被k整除的数的个数。这个通解思路在算法题里非常实用所以我想单独展开讲一下。5.1 前缀函数divCount(n, k)与通式推导定义divCount(n, k)为区间[0, n]内能被k整除的数的个数。这些数构成等差数列0, k, 2k, 3k, …。从 0 到 n 一共n 1个数每k个数里有一个整除的包括 0 本身所以divCount(n, k) (n 1) / k 1仔细看这个加 1因为区间从 0 开始0 也算一个“被整除的数”相当于把数列整体向右平移了一位。举个例子n 10, k 3时能被 3 整除的数是 0, 3, 6, 9共 4 个。套公式(10 1) / 3 1 3 1 4整数除法正确。于是原题答案countDivisible(low, high, k) divCount(high, k) - divCount(low - 1, k)把式子展开得countDivisible(low, high, k) (high 1) / k 1 - (low / k 1) (high 1) / k - low / k注意这里第二项的1和第一项的1刚好抵消所以最终表达式中不再出现额外的1。这解释了为什么有些版本的整除计数公式看起来那么简单——它把 0 的贡献在前缀差中自动消掉了。5.2 奇数公式其实是整除计数公式的特例回顾oddCount(n) (n 1) / 2这正是divCount(n, 2) - 1因为一般公式里有一个1而奇数里没有 0所以去掉。区间求奇数的最终公式(high 1) / 2 - low / 2也和countDivisible(low, high, 2)完全一致。这说明统计奇数并不是一个孤立的技巧而是“区间内倍数统计”这一大类问题的直接应用。我在刷题时发现很多题目表面上看起来各不相干比如求区间内能被 3 整除的个数、求区间内完全平方数的个数、求区间内素数的个数但它们几乎都能转化成一个前缀函数做差的形式。区别只在于每个前缀函数本身如何高效求解。抓住这个共同点刷题效率会高很多。5.3 变体问题一网打尽偶数、倍数、特殊条件统计偶数区间内偶数个数 区间长度 - 奇数个数也就是(high - low 1) - ((high 1) / 2 - low / 2)。化简后是high / 2 - (low - 1) / 2如果你愿意也可以单独记这个式子。统计能被 3 整除的数直接套用(high 1) / 3 - low / 3。统计完全平方数求floor(sqrt(high)) - ceil(sqrt(low)) 1本质也是前缀函数差。统计二进制表示中末尾是 1 的数这本质上就是奇数和本题完全相同。这些变体在面试中经常以不同包装出现理解了本题的数学结构等于掌握了一系列题目的钥匙。6. 与暴力解的性能对比与优化思路一个可复用的分析框架很多人会问既然 O(1) 公式这么简单为什么还要学暴力解我的看法是暴力解的价值不在于提交而在于验证——当你推导出公式后用暴力解在随机数据上对拍是检验公式正确性的最可靠手段。这种“暴力对拍 公式优化”的流程是我刷算法题时常用的标准打法。6.1 实测数据对比与复杂度分析我写了一个本地小工具统计不同区间规模下的运行时间环境是普通笔记本语言用 C数据大致如下区间规模暴力解法耗时公式解法耗时加速比10^3微秒级微秒级约 1 倍10^6约 1 ms约 0.001 ms约 1000 倍10^8约 80 ms约 0.001 ms约 80000 倍2^31无法在合理时间完成约 0.001 ms极高暴力解的时间复杂度是 O(high - low 1)空间复杂度 O(1)公式解的时间复杂度是 O(1)空间复杂度 O(1)。当区间规模超过 10^7 时两者的差距已经不在一个量级。这道题在力扣上的数据范围正是为了引导你往数学解法去想——区间上限达到 10^9暴力循环几乎注定超时。6.2 对拍测试的完整思路如何无脑验证公式正确性具体做法很简单写两个函数一个用暴力循环一个用数学公式然后在随机生成的low和high上反复比较结果。下面是一段 Python 对拍脚本框架import random def brute(low, high): return sum(1 for x in range(low, high 1) if x % 2 1) def formula(low, high): return (high 1) // 2 - low // 2 for _ in range(10000): low random.randint(0, 1000) high random.randint(low, 1000) if brute(low, high) ! formula(low, high): print(mismatch, low, high) break else: print(all ok)对拍看起来“笨”但它是验证数学推导的黄金标准。每次写完数学公式题我都建议跑一遍对拍尤其是在区间限定条件较复杂时能迅速暴露边界处理上的失误。6.3 面试中如何展示思路从暴力到优化的表达框架如果面试遇到这道题建议按这样的节奏回答先给出暴力解分析复杂度然后提出前缀差想法手动推导公式最后用几个边界用例验证。这个过程既展示了代码能力又体现了数学思维。我曾经在一次模拟面试中使用过这个套路面试官追问“如果low和high是长整型怎么办”我顺势将代码改成long版本的公式并解释溢出风险。这种“预判提问并主动补强”的表现比直接背答案更有说服力。面试官通常不会只满足于你能说出正确答案他们更想看到你对边界条件、语言特性和复杂度分析的敏锐度。7. 从这道题延伸出去数论思维如何提升刷题效率最后想聊聊这道题背后更值得培养的能力——把具体问题抽象成数学问题的思维模式。很多基础算法题比如求最大公约数、判断素数、计算组合数本质上都是数论问题它们的共同特点是存在一个利用数学规律直接计算的 O(1) 或 O(log n) 解法而暴力穷举往往不是最优路径。7.1 数论题的共性解题套路前缀函数、整除、周期数论题最常见的套路有三个前缀函数做差、整除分块、周期性规律。本题用的是前两个的朴素结合。当你看到一个题目要求“统计区间内满足某性质的数”第一反应应该是考虑能否定义f(n)表示[0, n]内满足性质的个数然后用f(high) - f(low - 1)求解。这比从区间本身下手要容易得多因为f(n)往往存在闭式解。7.2 养成“先想数学再写循环”的编码习惯不少初学者拿到题目就开写 for 循环这其实是个不太好的习惯。我现在的做法是先看数据范围如果区间长度超过 10^6就先停下来想一想有没有数学规律可循如果实在想不出再退而求其次写暴力解并标注其复杂度风险。这个习惯帮我避免了很多无谓的超时提交。这道“区间范围内统计奇数数目”虽然简单但它包含的数学建模思想可以平移到大量中高难度题目上。每一次使用前缀差、整除性质、周期规律都是在训练一种“用数学简化计算”的本能。把这些基础题吃透远比盲目刷几十道陌生题更有价值。7.3 最后的实战提示记住公式但更要记住推导路径如果你只是想通过这道题记住(high 1) / 2 - low / 2就够了如果你想提升算法能力建议把推导过程刻在脑子里定义前缀函数 → 推出通项公式 → 用前缀差求解区间 → 验证边界。这样即使题目换成统计偶数、统计能被 3 整除的数、统计完全平方数你也能迅速举一反三。我每次看到“统计区间”这四个字条件反射就是先画一条数轴标出 0 的位置然后手动推一遍[0, n]的性质。这道题我前前后后给不同模拟项目里的同学讲过很多遍反馈最集中的一条是“原来公式不是背出来的是推出来的。”希望这篇文章也能帮你建立同样的感觉——不只是会做这一道题而是掌握一类题的底层逻辑。