LeetCode 题解工作台
在区间范围内统计奇数数目
给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。 示例 1： 输入： low = 3, high = 7 输出： 3 解释： 3 到 7 之间奇数数字为 [3,5,7] 。 示例 2： 输入： low = 8, high = 10 输出： 1 解…
1
题型
8
代码语言
3
相关题
当前训练重点
简单 · 数学·driven
答案摘要
我们知道，在 $[0, x]$ 范围内奇数的个数为 。因此，$[low, high]$ 范围内奇数的个数为 $\lfloor\frac{high+1}{2}\rfloor - \lfloor\frac{low}{2}\rfloor$。 时间复杂度 ，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。
示例 1：
输入：low = 3, high = 7 输出：3 解释：3 到 7 之间奇数数字为 [3,5,7] 。
示例 2：
输入：low = 8, high = 10 输出：1 解释：8 到 10 之间奇数数字为 [9] 。
提示：
0 <= low <= high <= 10^9
解题思路
方法一：前缀和思想
我们知道，在 范围内奇数的个数为 。因此， 范围内奇数的个数为 。
时间复杂度 ，空间复杂度 。
class Solution:
def countOdds(self, low: int, high: int) -> int:
return ((high + 1) >> 1) - (low >> 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) because the count is calculated using a formula without iteration. Space complexity is O(1) as only a few integer variables are needed. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to recognize parity and inclusive range handling.
- question_mark
Look for O(1) arithmetic-based solutions instead of loops.
- question_mark
Clarify edge cases when low or high is odd or even.
常见陷阱
外企场景- error
Iterating through the entire range, which is unnecessary and inefficient.
- error
Off-by-one errors when handling inclusive endpoints.
- error
Miscounting when low and high are both odd or both even.
进阶变体
外企场景- arrow_right_alt
Count even numbers instead by adjusting the formula accordingly.
- arrow_right_alt
Count numbers divisible by k in a given interval using a similar math-driven approach.
- arrow_right_alt
Find the sum of odd numbers in the interval instead of just the count.