题目：
给你两个非负整数 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
思路：
如果我们暴力枚举 [low, high]中的所有元素会超出时间限制。
我们可以使用前缀和思想来解决这个问题，定义pre(x) 为区间 [0, x]中奇数的个数，很显然：
pre(x)=(x+1)/2;
故答案为 pre(high) - pre(low−1)。
java代码：
class Solution {
public int countOdds(int low, int high) {
return pre(high) - pre(low - 1);
}
public int pre(int x) {
return (x + 1) >> 1; //相当于(x+1)/2, 但效率更高
}
}
网友评论