DeepSeek LeetCode 3739. 统计主要元素子数组数目 II Java实现

问题理解题目给定整数数组 nums 和目标值 target返回 nums 中满足 target 是主要元素的非空子数组数量。主要元素定义在子数组中出现次数严格大于其长度的一半。---核心思路转换为前缀和问题将 nums 转换为一个新数组 a· 若 nums[i] target则 a[i] 1· 否则 a[i] -1此时一个子数组中 target 是主要元素 ⇔ 该子数组在 a 中的元素和 严格大于 0。设前缀和数组 prepre[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)有序列表javaimport java.util.*;class Solution {public long countMajoritySubarrays(int[] nums, int target) {// 有序列表维护所有已出现的前缀和ListInteger sortedPrefixes new ArrayList();sortedPrefixes.add(0); // pre[0] 0long ans 0;int pre 0; // 当前前缀和for (int num : nums) {pre (num target ? 1 : -1);// 在有序列表中查找第一个 pre 的位置// 该位置之前的所有前缀和都 preint 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) 查询javaclass Solution {public long countMajoritySubarrays(int[] nums, int target) {int n nums.length;int offset n 1; // 将范围 [-n, n] 映射到 [1, 2n1]long[] cnt new long[2 * n 3];long[] acc new long[2 * n 3];int pre offset; // 初始前缀和为0映射到 offsetcnt[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] 的对数· r1: pre -1前面 -1 的没有 → 0· r2: pre0前面 0 的有 -1 → 1· r3: pre1前面 1 的有 -1, 0, 0 → 3· r4: pre0前面 0 的有 -1 → 1· 总计 0 1 3 1 5 ✅