DeepSeek LeetCode 3739. 统计主要元素子数组数目 II Java实现
问题理解
题目：给定整数数组 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 ✅