LeetCode 1523. 在区间范围内统计奇数数目
目录
题目描述
题意分析
给两个非负整数
low和high，返回闭区间[low, high]内奇数的个数。区间是闭的——两端都算在内，这一点直接决定了公式里的+1放在哪。
约束是全题最重要的信号：
0 <= low <= high <= 10^9。区间长度可以达到 $10^9$，所以任何逐个遍历的写法都会超时。题目保证了low <= high，不必处理空区间；但low可以是 0，high可以取到 $10^9$，high + 1的中间值必须确认不溢出 32 位整数（$10^9 + 1$ 远小于 $2.1 \times 10^9$，安全）。
这个范围把题目从「遍历计数」逼成了「$O(1)$ 公式」。所以真正要想清楚的只有一件事：如何用一个不含循环的表达式表示区间内的奇数个数。
边界情形值得先列出来，它们是验证公式对错的试金石：
low和high都是奇数（如[3, 7]，答案 3）；都是偶数（如[2, 8]，答案 3）；一奇一偶（[3, 8]答案 3，[2, 7]答案 3）；low == high且为奇数（答案 1）；low == high且为偶数（答案 0）；low == 0（不能出现low - 1 = -1参与整数除法，否则不同语言的负数取整规则会导致结果不一致）。
解法：前缀奇数计数公式
核心思路
暴力是从
low循环到high逐个判奇偶，$O(high - low)$。区间长度可达 $10^9$，必然超时。
转向公式的标准手法是前缀化：先定义一个只依赖单个端点的函数
f(x) = [0, x]内的奇数个数，那么答案就是差值f(high) - f(low - 1)。这是区间统计问题的通用套路——把「区间」拆成「两个前缀之差」，把二元问题降成一元问题。
接下来求
f(x)。从 0 开始的整数序列0, 1, 2, 3, ...中奇偶严格交替，且偶数打头。所以在[0, x]这x + 1个数里，奇数恰好占一半（向下取整）：f(x) = (x + 1) / 2（整数除法）。验证一下：f(0) = 1/2 = 0（只有 0，没有奇数）；f(1) = 2/2 = 1（有 1）；f(2) = 3/2 = 1；f(3) = 4/2 = 2（1 和 3）。全部正确。
代入得
answer = (high + 1) / 2 - low / 2——注意f(low - 1) = ((low - 1) + 1) / 2 = low / 2，这一步化简顺带消灭了low - 1，从而避免了low = 0时出现-1参与整数除法的隐患（C/Java/Go 的整数除法都是向零取整，-1 / 2 = 0碰巧也对，但把它化简掉更干净，也免去了跨语言的取整规则讨论）。
于是最终公式是：
\[answer = \left\lfloor \frac{high + 1}{2} \right\rfloor - \left\lfloor \frac{low}{2} \right\rfloor\]
它的直观含义可以这样读：
(high + 1) / 2是「不超过high的奇数个数」，low / 2是「严格小于low的奇数个数」，两者相减正好是落在[low, high]内的奇数个数。整个推导没有任何分支——奇偶性的四种组合全部被整数除法的向下取整自动吸收，这是本题最值得欣赏的地方：好的公式让特判消失，而不是把特判写全。
解题步骤
- 确认不能遍历：先从约束读出区间长度上界 $10^9$，明确目标是 $O(1)$。这一步在面试里要说出来，它解释了为什么要推公式。
- 把区间拆成前缀差：
answer = f(high) - f(low - 1)，其中f(x)是[0, x]内的奇数个数。这是通法，不是本题特有的技巧。- 推导
f(x) = (x + 1) / 2：[0, x]共x + 1个数，从偶数 0 开始奇偶交替，奇数占其中一半向下取整。这里的+1来自闭区间含 0 这个端点。- 化简
f(low - 1)为low / 2：代入即得，同时消掉了low - 1，避开low = 0时的负数除法。- 直接返回
(high + 1) / 2 - low / 2：整数除法自动向下取整，不需要任何奇偶判断，也不需要Math.floor。本题范围仍能被double精确表示，但引入浮点只会增加类型转换和边界推理，没有收益。- 确认不溢出：
high + 1最大 $10^9 + 1$，在int范围内。
以
low = 3、high = 7走一遍（期望答案 3，即 3、5、7）。
f(high) = (7 + 1) / 2 = 4，含义是[0, 7]内有 4 个奇数：1、3、5、7。
f(low - 1) = f(2) = low / 2 = 3 / 2 = 1，含义是[0, 2]内有 1 个奇数：1。
相减得4 - 1 = 3，正是 3、5、7 这三个。
再用
low = 8、high = 10检验偶数端点（期望答案 1，即 9）：
(10 + 1) / 2 = 11 / 2 = 5，即[0,10]内的奇数 1、3、5、7、9 共 5 个。
8 / 2 = 4，即[0,7]内的奇数 1、3、5、7 共 4 个。
相减得 1，正确。
最后检验
low = 0、high = 0（期望 0）：(0 + 1) / 2 = 0，0 / 2 = 0，相减得 0。如果公式写成含(low - 1 + 1) / 2而没有化简，这里会出现f(-1)，虽然0 / 2仍是 0 没出错，但一旦有人把它写成(low - 1) / 2 + 1之类的变体，负数就会引发跨语言的取整差异。化简后的形式彻底回避了这类风险。
代码实现
class Solution {
public int countOdds(int low, int high) {
// (high+1)/2 是 [0, high] 内的奇数个数，low/2 是 [0, low-1] 内的奇数个数。
// 整数除法自动向下取整，四种奇偶组合无需分支。
return (high + 1) / 2 - low / 2;
}
}
func countOdds(low int, high int) int {
// (high+1)/2 是 [0, high] 内的奇数个数，low/2 是 [0, low-1] 内的奇数个数。
// 整数除法自动向下取整，四种奇偶组合无需分支。
return (high+1)/2 - low/2
}
复杂度分析
- 时间复杂度：$O(1)$。两次整数除法、一次加法、一次减法，与区间长度完全无关。相比 $O(high - low)$ 的遍历，在 $10^9$ 长度下这是能否通过的分水岭。
- 空间复杂度：$O(1)$。没有任何额外分配，连临时变量都不需要——整个函数体就是一个表达式。
关键点总结
- 区间统计 = 两个前缀统计之差。这是本题最值得带走的通法：定义
f(x)为[0, x]的统计量，答案就是f(high) - f(low - 1)。它同时适用于计数、求和、求积（改成除法）等各种可加统计量，303、304、1480 都是同一条思路的展开。- 让整数除法的向下取整替你做分类讨论。
low/high的奇偶共四种组合，很多人会写成四个if分支；而(high + 1) / 2 - low / 2一次覆盖全部。写公式时优先寻找这种「取整自动吸收边界」的形式，代码短、错误面小。- 化简掉
low - 1，既避开low = 0时的负数除法，也让公式对称好记。凡是表达式里出现「端点减一」，都值得试试能不能代入化简掉。- 从约束反推算法量级。$10^9$ 的区间长度直接宣判了遍历解法的死刑，这类「范围大到只能上公式」的信号在数学题里非常普遍，读约束应当先于想解法。
- 警惕中间值溢出。本题
high + 1恰好安全，但若约束改成high <= 2^31 - 1，high + 1就会溢出，届时要改写成high / 2 + (high & 1) - low / 2或改用 64 位。面试时主动核算一遍中间值范围是很好的习惯。- 不要用浮点。
Math.ceil/Math.floor在 $10^9$ 量级虽然还在double的精确整数范围内，但引入浮点是毫无必要的风险，纯整数运算永远更可靠。
易错点总结
- 逐个遍历判奇偶：
low = 0、high = 10^9时循环十亿次，直接超时。功能对但过不了。- 公式写成
(high - low) / 2 + 1：low = 2、high = 8得3 + 1 = 4，而正确答案是 3（3、5、7）。这个式子只在两端都是奇数时碰巧正确。- 公式写成
(high + 1) / 2 - (low + 1) / 2：这是f(high) - f(low)，把low自身排除在外了。low = 3、high = 7得4 - 2 = 2，正确答案是 3——low本身是奇数时会少数一个。- 公式写成
high / 2 - low / 2：这是f(high - 1) - f(low - 1)，high自身被排除。low = 3、high = 7得3 - 1 = 2，同样少一个。- 对
low和high的奇偶写四个分支却漏掉某一种组合：例如只处理了「都是奇数」和「都是偶数」，low = 2、high = 7落到未覆盖的分支返回默认值 0。用统一公式就不会有这个问题。low - 1直接参与除法且未化简：low = 0时出现(-1 + 1) / 2尚可，但若写成(low - 1) / 2这类变体，负数在向零取整的语言里得到 0、在向下取整的语言（如 Python）里得到 -1，结果不一致且难以复现。- 用浮点做除法再取整：
(high + 1) / 2.0后再Math.floor，除了引入不必要的精度依赖，还容易在忘记强转时返回double导致编译失败或类型不匹配。- 误以为区间是开区间或半开区间：按
(low, high]计算会在low为奇数时少一个，[3, 7]返回 2 而不是 3。题面是闭区间，两端都要算。- 交换了
low和high的位置：题目已保证low <= high，但若代码里写成(low + 1) / 2 - high / 2，[3, 7]会返回2 - 3 = -1这种负数，明显不合理——答案必须非负，这也是一个很好的自检信号。- 把
high上限放大后仍用int：约束若改到 $2^{31}-1$，high + 1溢出成负数，返回值变成一个巨大的负数。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1480. 一维数组的动态和 | 简单 | 前缀思想的最裸形态，把「区间求和」的地基先打好 |
| 303. 区域和检索 - 数组不可变 | 简单 | 同为「前缀差回答区间查询」，但前缀值要靠预处理数组而非闭式公式 |
| 233. 数字 1 的个数 | 困难 | 同样是 f(high) - f(low-1) 的思路，但 f(x) 需要按数位逐位推导 |
| 400. 第 N 位数字 | 中等 | 反过来由累计计数定位具体位置，考察分段计数与下标换算 |
| 204. 计数质数 | 中等 | 统计对象换成质数，没有闭式公式，必须用埃氏筛批量标记 |
| 172. 阶乘后的零 | 中等 | 同为把计数问题化归为整除表达式，靠不断除以 5 累加而非单个公式 |