企业官网建设流程全解析

昨天整理基础算法题库时，又碰到了这道“在区间范围内统计奇数数目”。题目本身很简单：给定两个非负整数 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的结果是 1（Python 取余结果符号跟随除数）；可如果面试官用的是另一种规则，-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. 公式可视化验证与边界情形：用具体数字建立直觉

数学公式推导完毕，但为了让直觉更扎实，我建议你亲手在纸上列几个区间，把暴力解和公式解的结果对齐一遍。下面这张表格覆盖了常见的边界情况，我每次讲这道题时都会拿它来做验证。

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 这两个，同样不包含 4（4 本身是偶数，本来也不在奇数列表里）。所以无论起点奇偶，公式都能精确算出区间内的奇数个数。这种“边界自动修正”的特性，正是前缀差公式的魅力所在。

3.2 从奇数映射到等差数列的角度再理解一遍

换个视角来看这个问题：区间[low, high]里的奇数，本质上是一个首项为low（如果low是奇数）或low+1（如果low是偶数）、公差为 2 的等差数列。最后一项不超过high。这个数列的项数就是题目答案。

等差数列求项数的公式是(末项 - 首项) / 公差 + 1，所以你也可以先判断首项、末项的奇偶，再代入公式。但这样做需要处理四种组合，分类讨论比较繁琐。相比之下，前缀差公式只需要两次整数除法和一次减法，简洁得多。我在面试中更喜欢用前缀差，因为它不需要在脑子里做奇偶分支判断，代码写出来也短。

4. 代码实现的细节与语言差异：溢出、整除方向与可读性

公式理清楚之后，代码实现基本就是照抄。但不同语言的整数除法规则略有差异，尤其是负数场景下可能产生误导，所以这里单独列一节讲编码细节。

4.1 主流语言的参考实现

Python 实现：

def count_odds(low: int, high: int) -> int: return (high + 1) // 2 - low // 2

Python 的//是向下取整除法，对于非负整数来说等价于整数除法。因为题目限定了非负整数，所以写起来最干净。

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) / 2，high + 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：答案 0；
• low = 0, high = 1：答案 1；
• low = 1, high = 1：答案 1；
• low = 1, high = 2：答案 1；
• low = 2, high = 2：答案 0；
• low = 0, high = 1000000000：答案 500000000；
• low = 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++），数据大致如下：

暴力解的时间复杂度是 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]的性质。这道题我前前后后给不同模拟项目里的同学讲过很多遍，反馈最集中的一条是：“原来公式不是背出来的，是推出来的。”希望这篇文章也能帮你建立同样的感觉——不只是会做这一道题，而是掌握一类题的底层逻辑。