问题理解

题目：给定整数数组 nums 和目标值 target，返回 nums 中满足 target 是主要元素的非空子数组数量。

主要元素定义：在子数组中出现次数严格大于其长度的一半。

---

核心思路：转换为前缀和问题

将 nums 转换为一个新数组 a：

· 若 nums[i] == target，则 a[i] = 1
· 否则 a[i] = -1

此时，一个子数组中 target 是主要元素 ⇔ 该子数组在 a 中的元素和 严格大于 0。

设前缀和数组 pre，pre[i] 表示 a[0..i-1] 的和（pre[0]=0）。子数组 (l, r] 的和为 pre[r] - pre[l]，要求 pre[r] - pre[l] > 0，即 pre[l] < pre[r]。

问题转化为：对每个位置 r，统计前面有多少个 l 满足 pre[l] < pre[r]，累加即为答案。

---

Java 实现（O(n log n)，有序列表）

```java
import java.util.*;

class Solution {
    public long countMajoritySubarrays(int[] nums, int target) {
        // 有序列表，维护所有已出现的前缀和
        List<Integer> sortedPrefixes = new ArrayList<>();
        sortedPrefixes.add(0);  // pre[0] = 0
        
        long ans = 0;
        int pre = 0;  // 当前前缀和
        
        for (int num : nums) {
            pre += (num == target ? 1 : -1);
            // 在有序列表中查找第一个 >= pre 的位置
            // 该位置之前的所有前缀和都 < pre
            int idx = Collections.binarySearch(sortedPrefixes, pre);
            if (idx < 0) {
                idx = -idx - 1;
            }
            ans += idx;
            // 将当前前缀和插入到有序列表中
            sortedPrefixes.add(idx, pre);
        }
        
        return ans;
    }
}
```

复杂度：时间 O(n log n)，空间 O(n)。

---

更优实现（O(n)，计数数组）AC

由于前缀和取值范围为 [-n, n]，可用计数数组实现 O(1) 查询：

```java
class Solution {
    public long countMajoritySubarrays(int[] nums, int target) {
        int n = nums.length;
        int offset = n + 1;  // 将范围 [-n, n] 映射到 [1, 2n+1]
        long[] cnt = new long[2 * n + 3];
        long[] acc = new long[2 * n + 3];
        
        int pre = offset;  // 初始前缀和为0，映射到 offset
        cnt[pre] = 1;
        acc[pre] = 1;
        
        long ans = 0;
        for (int num : nums) {
            pre += (num == target ? 1 : -1);
            // cnt[pre] 是当前前缀和出现的次数（包括当前这次）
            // acc[pre-1] 是所有小于当前前缀和的前缀和出现次数之和
            acc[pre] = acc[pre - 1] + ++cnt[pre];
            ans += acc[pre - 1];
        }
        return ans;
    }
}
```

复杂度：时间 O(n)，空间 O(n)。

---

示例验证

以 nums = [1,2,2,3], target = 2 为例：

· 转换后：[-1, 1, 1, -1]
· 前缀和：0, -1, 0, 1, 0
· 统计 pre[l] < pre[r] 的对数：
  · r=1: pre= -1，前面 < -1 的没有 → 0
  · r=2: pre=0，前面 < 0 的有 -1 → 1
  · r=3: pre=1，前面 < 1 的有 -1, 0, 0 → 3
  · r=4: pre=0，前面 < 0 的有 -1 → 1
· 总计 = 0 + 1 + 3 + 1 = 5 ✅