目标
给你一个整数数组 nums 和一个整数 target。
返回数组 nums 中满足 target 是 主要元素 的 子数组 的数目。
一个子数组的 主要元素 是指该元素在该子数组中出现的次数 严格大于 其长度的 一半 。
子数组 是数组中的一段连续且 非空 的元素序列。
示例 1:
输入: nums = [1,2,2,3], target = 2
输出: 5
解释:
以 target = 2 为主要元素的子数组有:
nums[1..1] = [2]
nums[2..2] = [2]
nums[1..2] = [2,2]
nums[0..2] = [1,2,2]
nums[1..3] = [2,2,3]
因此共有 5 个这样的子数组。示例 2:
输入: nums = [1,1,1,1], target = 1
输出: 10
解释:
所有 10 个子数组都以 1 为主要元素。示例 3:
输入: nums = [1,2,3], target = 4
输出: 0
解释:
target = 4 完全没有出现在 nums 中。因此，不可能有任何以 4 为主要元素的子数组。故答案为 0。说明:
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 10^9
- 1 <= target <= 10^9
思路
定义子数组的 主要元素 为出现次数 严格大于 子数组长度一半 的元素。有一个数组 nums，找出以 target 为主要元素的子数组个数。
使用前缀和记录 target 的出现次数，保留循环子数组，判断 target 是否是它的主要元素即可。
代码
/**
* @date 2026-06-25 9:12
*/
public class CountMajoritySubarrays3737 {
public int countMajoritySubarrays(int[] nums, int target) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (nums[i] == target ? 1 : 0);
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int l = j - i + 1;
if (prefix[j + 1] - prefix[i] > l / 2) {
res++;
}
}
}
return res;
}
}
性能
