如何求解数组中所有长度为m的连续子数组的元素最高频率序列

核心方案：滑动窗口 + 双哈希表 #

这是典型的固定长度滑动窗口统计问题，用滑动窗口复用前一次的统计结果，时间复杂度可以做到O(n)，远优于暴力枚举的O(n*m)，具体实现逻辑如下：

所需变量 #

• count：哈希表，键为数组元素，值为该元素在当前窗口内的出现次数
• freq：哈希表，键为出现次数，值为当前窗口内出现次数等于该键的元素总数
• max_freq：整数，记录当前窗口的最大出现次数
• res：结果数组，存储每个窗口对应的最高频率

执行步骤 #

1. 初始化首个窗口
   遍历数组前m个元素，逐个更新计数与频率：

• 每处理一个元素num，如果它已存在于count中，先将freq[count[num]]减1，值为0时直接删除该键
• count[num]计数加1
• freq[count[num]]计数加1
• 同步更新max_freq为当前最大的count[num]
  首个窗口处理完成后，将max_freq加入res。

2. 滑动遍历剩余元素
   从下标m开始遍历到数组末尾，每次窗口右移一位，依次处理滑出的左边界元素和滑入的右边界元素：

处理滑出元素 left_num = arr[i - m]

1. 将freq[count[left_num]]减1，值为0时删除该键
2. 如果滑出元素的原计数等于max_freq，且freq中已经不存在max_freq这个键，说明当前没有元素达到原有最大频率，max_freq减1
3. count[left_num]减1，值为0时直接从count中删除该元素，否则将freq[count[left_num]]加1

处理滑入元素 right_num = arr[i]

1. 如果right_num已存在于count中，先将freq[count[right_num]]减1，值为0时删除该键
2. count[right_num]加1
3. freq[count[right_num]]加1
4. 如果当前count[right_num]大于max_freq，更新max_freq为该值
   处理完成后将当前max_freq加入res。
5. 遍历结束后直接返回res即可。

常见问题排查 #

你之前的方案用两个HashMap存队列和行和，大概率是没有维护好计数和频率的对应关系，也没有正确处理最大频率元素滑出窗口的边界场景，按照上面的逻辑调整就能覆盖所有测试用例。

内容的提问来源于stack exchange，提问作者Adrian Sowandi