LeetCode 每日一题笔记 日期：2026.06.25 题目：3737. 统计主要元素子数组数目 I

LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.25
• 题目：3737. 统计主要元素子数组数目 I
• 难度：中等
• 标签：数组、前缀和、哈希表

1. 题目理解

问题描述
给定数组nums和整数target，统计连续非空子数组数量，满足target是该子数组的主要元素。
主要元素定义：该数字在子数组出现次数严格大于子数组长度的一半。
转换条件：将target记 +1，其余数字记 -1，子数组区间前缀和 > 0 等价于满足条件。

示例

输入：nums = [1,2,2,3], target = 2
输出：5
解释：合法子数组为 [2]、[2]、[2,2]、[2,2,3]、[1,2,2]，共5个。

2. 解题思路

核心观察

1. 数值映射：nums[j]==target→ +1，其他 → -1；区间和>0 即满足主要元素条件。
2. 暴力双层循环枚举全部子数组，累加合法计数；优化方案用前缀和+哈希表将复杂度从O(n2)O(n^2)O(n2)降至O(n)O(n)O(n)。
3. 设前缀和preSum[j]，区间[i,j]和 >0 等价preSum[j] - preSum[i-1] > 0→preSum[i-1] < preSum[j]。

算法步骤

暴力版：

1. 枚举子数组起点i；
2. 从i向后累加映射值sum；
3. sum>0则计数+1；
4. 遍历完成返回总数。

优化前缀和哈希版：

1. 维护前缀和与哈希表统计历史前缀和频次；
2. 遍历更新当前前缀和，累加哈希表中小于当前值的前缀和数量；
3. 将当前前缀和存入哈希表，最终返回总计数。

3. 代码实现

packagelc3737;classSolution{publicintcountMajoritySubarrays(int[]nums,inttarget){intn=nums.length;intans=0;for(inti=0;i<n;i++){intsum=0;for(intj=i;j<n;j++){sum+=nums[j]==target?1:-1;if(sum>0)ans++;}}returnans;}}

4. 代码优化说明

importjava.util.HashMap;classSolution{publicintcountMajoritySubarrays(int[]nums,inttarget){// 哈希表存储前缀和出现次数，初始前缀和0出现1次HashMap<Integer,Integer>map=newHashMap<>();map.put(0,1);intpreSum=0,res=0;for(intnum:nums){// 映射转换，简化三元运算分支preSum+=num==target?1:-1;// 累加所有小于当前preSum的历史前缀和数量，替代内层循环map.forEach((k,v)->{if(k<preSum)res+=v;});map.put(preSum,map.getOrDefault(preSum,0)+1);}returnres;}}

5. 复杂度分析

• 双层暴力循环原版
  时间复杂度：O(n2)O(n^2)O(n2)，两层嵌套枚举所有子数组，适合小数组；存在内层if判断分支。
  空间复杂度：O(1)O(1)O(1)，仅常数临时变量。
• 前缀和哈希优化版
  时间复杂度：O(n)O(n)O(n)，单次遍历数组，哈希查询统计替代二层循环，大幅减少循环次数。
  空间复杂度：O(n)O(n)O(n)，哈希表存储全部前缀和；消除二层循环，仅保留必要条件判断。

6. 总结

• 核心：数值映射转化问题为区间前缀和大于0计数；
• 优化亮点：前缀和+哈希表消去二层循环，降低时间复杂度；减少循环嵌套分支，提升大数据下运行效率；
• 关键转换：target次数 > 子数组长度/2等价区间映射和 > 0，是解题核心数学转化。