🤖 AI总结
主题
力扣4011题：按奇偶比统计满足条件的连续子数组数量。
摘要
通过奇偶权重映射将条件转化为子数组和≥0，利用前缀和与归并排序统计合法数对，实现O(n log n)解法。
关键信息
- 1 将奇偶权重映射后，条件转化为子数组和≥0，并用前缀和与归并排序计数。
- 2 不含奇数的片段因权重和为负被自动排除，无需额外判断。
- 3 时间复杂度O(n log n)，空间复杂度O(n)，并给出Go、Python、C++代码。
2026-11-01：按奇偶比统计子数组Ⅰ。用go语言，给定一个整数序列，以及两个整数 a 和 b。考察该序列中任意一段连续且至少包含一个元素的片段。设该片段中偶数个数为 x，奇数个数为 y。要求该片段至少包含一个奇数，也就是 y 大于 0；同时把 x 与 y 形成的比值和 a 与 b 形成的比值按精确分数值比较，前者不能大于后者。统计所有满足这些条件的连续片段数量，并返回该数量。
1 <= nums.length <= 1000。
1 <= nums[i] <= 1000。
1 <= a, b <= 1000。
输入： nums = [1,2,1,2], a = 3, b = 2。
输出： 7。
解释：
以下子数组是有效的：
子数组
元素
偶数数量
奇数数量
比例
nums[0..0]
0
1
nums[0..1]
[1, 2]
1
1
1 / 1
nums[0..2]
[1, 2, 1]
1
2
1 / 2
nums[0..3]
[1, 2, 1, 2]
2
2
2 / 2
nums[1..2]
[2, 1]
1
1
1 / 1
nums[2..2]
0
1
nums[2..3]
[1, 2]
1
1
1 / 1
因此，有效子数组的数量为 7。
题目来自力扣4011。
大体步骤如下： 一、给每个元素”赋权”，把条件变成”子数组和 ≥ 0″
把序列做一次映射：
• 偶数 → 权重−b
• 奇数 → 权重+a
（代码里用x&1作下标在[-b, a]里取值，偶数取下标 0 得 −b，奇数取下标 1 得 +a）
那么一个片段内所有元素权重之和恰好是：
a·y − b·x
于是”合法片段”就等价于一个极其干净的条件：
该片段的权重和 ≥ 0
二、”y > 0″为什么不需要额外判断
这是个容易漏掉的细节。如果一个片段一个奇数都没有（y = 0），又因为片段非空，必然 x ≥ 1，那么它的权重和 = −b·x。由于 b ≥ 1，这个值严格小于 0，一定不满足 “≥ 0″。
也就是说：所有不含奇数的片段会因为权重和为负而被自动筛掉，所以程序里完全不需要再写一次”至少一个奇数”的检查。条件本身已经把这件事做完了。
三、前缀和：把”子数组和”变成”两个前缀和之差”
构造长度 n+1 的前缀和数组sum：
• sum[0] = 0
• sum[i+1] = sum[i] + 权重(nums[i])
于是片段 nums[l..r] 的权重和 =sum[r+1] − sum[l]。
“权重和 ≥ 0” 就变成：
sum[r+1] ≥ sum[l]，其中 l < r+1
所以问题最终归约为一个经典计数问题：
在长度 N = n+1 的数组 sum 中，统计满足 i < j 且 sum[i] ≤ sum[j] 的数对 (i, j) 的个数。
每一对 (i, j) 唯一对应一个合法片段 nums[i..j−1]，两者一一对应，不重不漏。
顺带一提数值范围：权重绝对值不超过 1000，长度不超过 1000，前缀和绝对值 ≤ 10⁶，int 完全装得下；答案最多 n(n+1)/2 = 500500，转成 int64 返回只是图个稳妥。
四、归并排序顺便数数：为什么”排序”能数出数对
暴力做法是 O(N²) 双重循环。这里用的是分治 + 归并，在排序的同时把数对数量顺手算出来。
1. 分
把 sum 切成左右两半（各 clone 一份，因为后面要原地覆盖 sum，不拷贝就会被自己的写操作污染）。递归地：
• 统计完全落在左半内部的合法数对
• 统计完全落在右半内部的合法数对
2. 合（核心的计数逻辑）
剩下要统计的是”一个端点在左、一个端点在右”的数对。注意左半所有下标都小于右半所有下标，所以只要左半的某个值 ≤ 右半的某个值，就构成一个合法数对。
归并时从左到右往 sum 里填：
• 如果left[l] ≤ right[r]，就先把 left[l] 填进去，l 前进一格。此刻不加数。
• 否则（即right[r] < left[l]，或左半已经取完），就填 right[r]，并且cnt += l。
cnt += l的含义：此时左半已经有 l 个元素被填进了输出，这 l 个元素每一个都 ≤ 当前的 right[r]，因此它们与这个 right[r] 各构成一个合法数对，一共 l 对。
为什么”已填进去的 l 个左半元素”一定都 ≤ 当前 right[r]？因为右半是有序的、且是从左往右被消费的：那些左半元素当初被填进去时，各自 ≤ 当时的右半队首，而当时的队首 ≤ 现在的 right[r]，传递下来就得到结论。反过来，那些还没被填进去的左半元素，此刻的 left[l] 已经 > right[r]（或者左半已空），左半有序 ⇒ 它们全都 > right[r]，不构成数对。所以加 l 恰好不多不少。
两个容易忽略的点：
• 比较用≤而不是<，这样相等的前缀和也被计入（对应权重和恰好为 0 的片段，题目是”不能超过”，等于算合法）。
• 当左半取完、被迫一直取右半时，走的也是 else 分支，cnt += l会把整个左半的长度加进去，逻辑一致，不需要特判。
3. 副作用
归并过程把 sum 就地写成了有序的，这正是上一层归并所要求的（上一层需要左右两半各自有序）。所以”排序”不是副产品而是必需步骤，计数只是搭了顺风车。
五、用示例完整走一遍
nums = [1, 2, 1, 2]，a = 3，b = 2。奇偶权重：1→+3，2→−2，1→+3，2→−2。
前缀和数组：sum = [0, 3, 1, 4, 2]
数出所有 i < j 且 sum[i] ≤ sum[j] 的数对，共 7 对：
数对 (i, j)
权重和
对应片段
偶 x / 奇 y
校验 a·y − b·x
(0,1)
3 − 0 = 3
3 − 0 = 3 ≥ 0
(0,2)
1 − 0 = 1
[1, 2]
1 / 1
3 − 2 = 1 ≥ 0
(0,3)
4 − 0 = 4
[1, 2, 1]
1 / 2
6 − 2 = 4 ≥ 0
(0,4)
2 − 0 = 2
[1, 2, 1, 2]
2 / 2
6 − 4 = 2 ≥ 0
(1,3)
4 − 3 = 1
[2, 1]
1 / 1
3 − 2 = 1 ≥ 0
(2,3)
4 − 1 = 3
3 − 0 = 3 ≥ 0
(2,4)
2 − 1 = 1
[1, 2]
1 / 1
3 − 2 = 1 ≥ 0
而 (1,2)、(1,4)、(3,4) 这三对的差分别为 −2、−1、−2，权重和为负，被剔除；它们对应的片段 [2]、[2,1,2]、[2] 全是纯偶数片段（y = 0），正好印证了第三节”y > 0 自动成立”的说法。最终输出7，与题目答案一致。
六、复杂度
设原数组长 n，前缀和数组长 N = n + 1。
时间复杂度 O(n log n)
标准的归并排序结构：递归深度 log N 层，每层所有节点的归并总量加起来是 O(N)，合计 O(N log N)，即O(n log n)。构造前缀和是 O(n)，被它盖住。
额外空间复杂度 O(n)
• 每一层递归都要为左右两半各 clone 一份，单层总量 O(N)。
• 但同时存活的 clone 只沿一条递归路径累加：N + N/2 + N/4 + … < 2N，即 O(N)。
• 递归栈深度 O(log n)。
所以峰值额外空间是O(n)（这里的”额外”指不计输入数组本身；前缀和数组本身也是 O(n) 的额外开销，量级相同）。
补充一句：本题 n ≤ 1000，其实 O(n²) 的暴力（枚举两端 + 前缀和 O(1) 判定，约 5×10⁵ 次比较）也完全跑得过；归并写法的好处是把复杂度压到 O(n log n)，当 n 放大到 10⁵ 量级时依然可用。
Go完整代码如下：
package main
import (
"fmt"
"slices"
)
func mergeCount(sum []int)int {
n := len(sum)
if n <= 1 {
return0
}
left := slices.Clone(sum[:n/2])
right := slices.Clone(sum[n/2:])
cnt := mergeCount(left) + mergeCount(right) // left 和 right 各自的合法数对个数
l, r := 0, 0
for i := range sum {
// 计算一个在 left 中，另一个在 right 中的合法数对个数
if l < len(left) && (r == len(right) || left[l] <= right[r]) {
sum[i] = left[l]
l++
} else {
cnt += l // left[:l] 中的数都 <= right[r]，这有 l 个
sum[i] = right[r]
r++
}
}
return cnt
}
func countRatioSubarrays(nums []int, a, b int)int64 {
sum := make([]int, len(nums)+1)
value := [2]int{-b, a}
for i, x := range nums {
sum[i+1] = sum[i] + value[x&1] // 偶数视作 -b，奇数视作 a
}
returnint64(mergeCount(sum))
}func main() {
nums := []int{1, 2, 1, 2}
a := 3
b := 2
result := countRatioSubarrays(nums, a, b)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def merge_count(prefix):
n = len(prefix)
if n <= 1:
return0
mid = n // 2
left = prefix[:mid]
right = prefix[mid:]
# left 和 right 各自的合法数对个数
cnt = merge_count(left) + merge_count(right)
l = r = 0
for i in range(n):
# 计算一个在 left 中，另一个在 right 中的合法数对个数
if l < len(left) and (r == len(right) or left[l] <= right[r]):
prefix[i] = left[l]
l += 1
else:
cnt += l # left[:l] 中的数都 <= right[r]，共有 l 个
prefix[i] = right[r]
r += 1
return cnt
def count_ratio_subarrays(nums, a, b):
n = len(nums)
prefix = [0] * (n + 1)
# 偶数视作 -b，奇数视作 a
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + (-b if (x & 1) == 0else a)
return merge_count(prefix)
def main():
nums = [1, 2, 1, 2]
a = 3
b = 2
result = count_ratio_subarrays(nums, a, b)
print(result)if __name__ == "__main__":
main()
C++完整代码如下：
using namespace std;
long long mergeCount(vector & sum) {
int n = sum.size();
if (n <= 1) {
return0;
}
// 对应 Go 中 slices.Clone
vector left(sum.begin(), sum.begin() + n / 2);
vector right(sum.begin() + n / 2, sum.end());
// 左右两边各自的合法数对个数
long long cnt = mergeCount(left) + mergeCount(right);
int l = 0, r = 0;
for (int i = 0; i < n; i++) {
// 合并有序数组，同时统计跨左右两边的合法数对
if (l < (int)left.size() &&
(r == (int)right.size() || left[l] <= right[r])) {
sum[i] = left[l];
l++;
} else {
// left[0..l-1] 中的所有数都 <= right[r]，共有 l 个
cnt += l;
sum[i] = right[r];
r++;
}
}
return cnt;
}
long long countRatioSubarrays(const vector& nums, int a, int b) {
vector sum(nums.size() + 1, 0);
for (int i = 0; i < (int)nums.size(); i++) {
// 偶数视作 -b，奇数视作 a
long long value = (nums[i] % 2 != 0) ? a : -b;
sum[i + 1] = sum[i] + value;
}
return mergeCount(sum);
}
int main() {
vector nums = {1, 2, 1, 2};
int a = 3;
int b = 2;
long long result = countRatioSubarrays(nums, a, b);
cout << result << endl;return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
