以下是 LeetCode 3739. 统计主要元素子数组数目 II 的 C 语言实现。题目分析这道题要求统计数组 nums 中满足 target 是主要元素出现次数严格大于子数组长度的一半的子数组数目。核心思路1. 将数组中等于 target 的元素视为 1不等于的视为 -12. 问题转化为统计元素和 严格大于 0 的子数组个数3. 使用前缀和 树状数组Fenwick Tree/BIT来高效求解关键转换- 设前缀和为 s子数组 [l, r] 的和为 s[r1] - s[l]- 要求 s[r1] - s[l] 0即 s[r1] 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 增加 deltavoid 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]整体右移 n1 个单位变为 [1, 2n1]int offset numsSize 1; // 偏移量int size 2 * numsSize 1; // 树状数组大小BIT *bit bitCreate(size);// 初始前缀和为 0对应位置 offset计数为 1bitUpdate(bit, offset, 1);long long ans 0;int s offset; // 当前前缀和已偏移for (int i 0; i numsSize; i) {// 等于 target 则 1否则 -1s (nums[i] target) ? 1 : -1;// 查询前缀和小于当前 s 的数量即查询 [1, s-1] 的和ans bitQuery(bit, s - 1);// 将当前前缀和加入树状数组bitUpdate(bit, s, 1);}bitFree(bit);return ans;}复杂度分析指标 复杂度时间复杂度 O(n log n)每个元素进行两次树状数组操作每次 O(log n)空间复杂度 O(n)树状数组需要 2n1 的空间思路详解1. 问题转换设子数组中 target 出现 cnt 次长度为 len。条件 cnt len/2 等价于 2*cnt len。令 target 为 1其他为 -1则子数组和 0 即满足条件。2. 前缀和设前缀和数组 pre[i] 表示前 i 个元素的和。子数组 [l, r] 的和为 pre[r1] - pre[l]。3. 树状数组维护枚举右端点 r需要找满足 pre[l] pre[r1] 的左端点 l 的数量。用树状数组维护之前所有前缀和的出现次数支持- query(x)查询小于等于 x 的前缀和个数- update(x, 1)将当前前缀和加入4. 偏移处理前缀和范围是 [-n, n]树状数组下标从 1 开始所以整体偏移 n1。