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. 解题思路核心观察数值映射nums[j]target→ 1其他 → -1区间和0 即满足主要元素条件。暴力双层循环枚举全部子数组累加合法计数优化方案用前缀和哈希表将复杂度从O(n2)O(n^2)O(n2)降至O(n)O(n)O(n)。设前缀和preSum[j]区间[i,j]和 0 等价preSum[j] - preSum[i-1] 0→preSum[i-1] preSum[j]。算法步骤暴力版枚举子数组起点i从i向后累加映射值sumsum0则计数1遍历完成返回总数。优化前缀和哈希版维护前缀和与哈希表统计历史前缀和频次遍历更新当前前缀和累加哈希表中小于当前值的前缀和数量将当前前缀和存入哈希表最终返回总计数。3. 代码实现packagelc3737;classSolution{publicintcountMajoritySubarrays(int[]nums,inttarget){intnnums.length;intans0;for(inti0;in;i){intsum0;for(intji;jn;j){sumnums[j]target?1:-1;if(sum0)ans;}}returnans;}}4. 代码优化说明importjava.util.HashMap;classSolution{publicintcountMajoritySubarrays(int[]nums,inttarget){// 哈希表存储前缀和出现次数初始前缀和0出现1次HashMapInteger,IntegermapnewHashMap();map.put(0,1);intpreSum0,res0;for(intnum:nums){// 映射转换简化三元运算分支preSumnumtarget?1:-1;// 累加所有小于当前preSum的历史前缀和数量替代内层循环map.forEach((k,v)-{if(kpreSum)resv;});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是解题核心数学转化。