当前位置：首页 > news >正文

Kimi LeetCode 3739. 统计主要元素子数组数目 II C语言实现

news 2026/7/27 7:55:33

以下是 LeetCode 3739. 统计主要元素子数组数目 II 的 C 语言实现。

题目分析

这道题要求统计数组 `nums` 中满足 `target` 是主要元素（出现次数严格大于子数组长度的一半）的子数组数目。

核心思路：
1. 将数组中等于 `target` 的元素视为 `1`，不等于的视为 `-1`
2. 问题转化为：统计元素和严格大于 0 的子数组个数
3. 使用前缀和 + 树状数组（Fenwick Tree/BIT）来高效求解

关键转换：
- 设前缀和为 `s`，子数组 `[l, r]` 的和为 `s[r+1] - s[l]`
- 要求 `s[r+1] - s[l] > 0`，即 `s[r+1] > s[l]`
- 枚举右端点，用树状数组维护之前出现过的前缀和，查询小于当前前缀和的数量

C 语言实现

```c
#include <stdlib.h>
#include <string.h>

// 树状数组 (Fenwick Tree / Binary Indexed Tree)
typedef struct {
int n;
long long *c; // 使用 long long 防止溢出
} BIT;

// 初始化树状数组
BIT* bitCreate(int n) {
BIT *bit = (BIT*)malloc(sizeof(BIT));
bit->n = n;
bit->c = (long long*)calloc(n + 1, sizeof(long long));
return bit;
}

// 释放树状数组
void bitFree(BIT *bit) {
free(bit->c);
free(bit);
}

// 单点更新：在位置 x 增加 delta
void bitUpdate(BIT *bit, int x, long long delta) {
while (x <= bit->n) {
bit->c[x] += delta;
x += x & -x; // 加上 lowbit
}
}

// 前缀查询：查询 [1, x] 的和
long long bitQuery(BIT *bit, int x) {
long long res = 0;
while (x > 0) {
res += bit->c[x];
x -= x & -x; // 减去 lowbit
}
return res;
}

/**
* 统计主要元素子数组数目 II
* @param nums 整数数组
* @param numsSize 数组长度
* @param target 目标元素
* @return 满足条件的子数组数目
*/
long long countMajoritySubarrays(int* nums, int numsSize, int target) {
// 前缀和范围: [-n, n]，整体右移 n+1 个单位变为 [1, 2n+1]
int offset = numsSize + 1; // 偏移量
int size = 2 * numsSize + 1; // 树状数组大小

BIT *bit = bitCreate(size);

// 初始前缀和为 0，对应位置 offset，计数为 1
bitUpdate(bit, offset, 1);

long long ans = 0;
int s = offset; // 当前前缀和（已偏移）

for (int i = 0; i < numsSize; i++) {
// 等于 target 则 +1，否则 -1
s += (nums[i] == target) ? 1 : -1;

// 查询前缀和小于当前 s 的数量（即查询 [1, s-1] 的和）
ans += bitQuery(bit, s - 1);

// 将当前前缀和加入树状数组
bitUpdate(bit, s, 1);
}

bitFree(bit);
return ans;
}
```