[ 力扣 1124 ] 解锁最长良好时段问题：前缀和+哈希表的优雅解法-程序员充电站

解锁最长良好时段问题：前缀和+哈希表的优雅解法l

Bilibili 同步视频
一、问题溯源：读懂最长良好时段的核心要求
- 问题初转化：把次数比较变成数值运算
二、核心原理：前缀和——快速计算区间和的利器
- 1. 前缀和的定义
- 2. 前缀和求区间和的公式
- 3. 问题二次转化：前缀和数组上的新问题
三、进阶优化：利用前缀和特性+哈希表降维
- 核心思路总结
四、代码实现：C++版高效解法
- 完整C++代码
- 代码逐行讲解
- 算法性能分析
五、拓展思考：算法的灵活变通
六、总结

Bilibili 同步视频

[ 力扣 1124 ] 解锁最长良好时段问题：前缀和+哈希表的优雅解法

在算法刷题的路上，我们总会遇到一些看似复杂、实则暗藏巧思的数组问题，最长良好时段问题就是其中的经典代表。这类问题核心考察对序列的转化能力和前缀和技巧的灵活运用，初看让人无从下手，但若掌握了“状态转化+前缀和+哈希表”的组合拳，便能迎刃而解。今天，我们就从问题本质出发，一步步拆解解题思路，用C++实现高效解法，带你吃透这一经典题型✨。

一、问题溯源：读懂最长良好时段的核心要求

首先，我们要明确问题的定义：当一个时间段内，表现良好的次数大于表现不良好的次数时，该时间段为表现良好时段，要求找到最长的这一时间段。

为了方便理解，我们用具体的数值序列举例，比如题目中提到的9960669（可理解为每日表现评分，大于8为良好，小于等于8为不良），我们的目标就是从这个序列中，找到最长的连续子区间满足“良好次数>不良次数”。

问题初转化：把次数比较变成数值运算

直接统计“良好/不良次数”进行比较，会涉及大量的区间遍历和计数，时间复杂度极高。这里有一个关键巧思：将表现良好记为+1，表现不良好记为-1。

这样的转化让问题发生了本质变化：

原问题“良好次数>不良次数” → 转化后“连续子区间的和>0”

比如序列9960669转化为+1/-1序列为：[1,1,-1,-1,-1,-1,1]，此时我们只需找到这个序列中和大于0的最长连续子区间，就是原问题的答案。这一步转化是解题的基石，将计数比较问题转化为了经典的数组区间和问题💡。

二、核心原理：前缀和——快速计算区间和的利器

当问题转化为“找和大于0的最长连续子区间”后，我们需要一个能快速计算任意区间和的工具，前缀和就是为此而生的。它能将区间和的计算时间复杂度从O ( n ) O(n)O(n)降至O ( 1 ) O(1)O(1)，是处理数组区间和问题的必备算法。

1. 前缀和的定义

设转化后的+1/-1序列为A [ 0 ] , A [ 1 ] , … , A [ n − 1 ] A[0],A[1],\dots,A[n-1]A[0],A[1],…,A[n−1]，定义前缀和数组S SS，其中S [ 0 ] = 0 S[0]=0S[0]=0，S [ i ] S[i]S[i]表示序列A AA的前i ii项和，即：

S [ 0 ] = 0 S[0] = 0S[0]=0

S [ 1 ] = A [ 0 ] S[1] = A[0]S[1]=A[0]

S [ 2 ] = A [ 0 ] + A [ 1 ] S[2] = A[0]+A[1]S[2]=A[0]+A[1]

… \dots…

S [ i ] = A [ 0 ] + A [ 1 ] + ⋯ + A [ i − 1 ] S[i] = A[0]+A[1]+\dots+A[i-1]S[i]=A[0]+A[1]+⋯+A[i−1]

简单来说，前缀和数组的第i ii项，就是原数组前i − 1 i-1i−1项的累加和，S[0]=0是人为初始化的哨兵值，用于简化边界计算。

2. 前缀和求区间和的公式

对于原数组A AA的任意连续子区间[ l , r ] [l, r][l,r]（下标从0开始），其区间和可以通过前缀和数组快速计算：

s u m ( A [ l . . r ] ) = S [ r + 1 ] − S [ l ] sum(A[l..r]) = S[r+1] - S[l]sum(A[l..r])=S[r+1]−S[l]

原理图解：

原数组A：[A0, A1, A2, A3, A4] 前缀和S：[0, S1, S2, S3, S4, S5] 求A[1..3]的和：A1+A2+A3 = (A0+A1+A2+A3) - A0 = S4 - S1

从图中能清晰看到，区间[ l , r ] [l,r][l,r]的和，等于前缀和数组中“后点减前点”，这一特性让我们摆脱了对原数组的重复遍历。

3. 问题二次转化：前缀和数组上的新问题

结合前缀和的区间和公式，原问题“找A AA中sum>0的最长连续子区间[ l , r ] [l,r][l,r]”，可以转化为：

S [ r + 1 ] − S [ l ] > 0 ⟹ S [ r + 1 ] > S [ l ] S[r+1] - S[l] > 0 \implies S[r+1] > S[l]S[r+1]−S[l]>0⟹S[r+1]>S[l]

同时，子区间[ l , r ] [l,r][l,r]的长度为r − l + 1 = ( r + 1 ) − l r-l+1 = (r+1) - lr−l+1=(r+1)−l。

因此，原问题最终转化为：在前缀和数组S SS中，找到两个下标i ii和j jj（j > i j>ij>i），满足S [ j ] > S [ i ] S[j]>S[i]S[j]>S[i]，且j − i j-ij−i的差值最大——这个最大差值就是原问题的答案✅。

到这里，解题的核心思路已经清晰，我们把一个看似复杂的计数问题，一步步转化为了前缀和数组上的“找最长逆序对”问题，这就是算法转化的魅力。

三、进阶优化：利用前缀和特性+哈希表降维

现在问题聚焦到了前缀和数组S SS上，如何高效找到满足S [ j ] > S [ i ] S[j]>S[i]S[j]>S[i]且j − i j-ij−i最大的i , j i,ji,j？

首先，我们观察到前缀和数组的特殊性质：由于原数组A AA只有+1和-1，因此前缀和数组S SS的数值是连续变化的——即S [ i ] S[i]S[i]的取值只能是S [ i − 1 ] + 1 S[i-1]+1S[i−1]+1或S [ i − 1 ] − 1 S[i-1]-1S[i−1]−1。比如序列[1,1,-1,-1,-1,-1,1]的前缀和数组为S = [ 0 , 1 , 2 , 1 , 0 , − 1 , − 2 , − 1 ] S=[0,1,2,1,0,-1,-2,-1]S=[0,1,2,1,0,−1,−2,−1]，数值始终在相邻整数间变化。

基于这一特性，我们可以得出一个重要结论：对于前缀和数组中的某个值S [ j ] = n S[j]=nS[j]=n，要找到最小的i < j i<ji<j满足S [ i ] < n S[i]<nS[i]<n，只需从n − 1 n-1n−1开始向前找，找到第一个出现的小于n nn的值即可。

而要快速找到“每个值第一次出现的下标”，哈希表（unordered_map）是最优选择——我们用哈希表记录前缀和数组中每个值第一次出现的下标，因为要让j − i j-ij−i最大，必须保证i ii尽可能小（即第一次出现的位置）。

核心思路总结

将原序列转化为+1/-1序列，把次数比较变为区间和判断；
构建前缀和数组，将区间和问题转化为前缀和的差值比较；
用哈希表记录前缀和每个值第一次出现的下标，保证后续找到的区间长度最大；
遍历前缀和数组，对每个值S [ j ] S[j]S[j]，向前找小于它的第一个值，计算j − i j-ij−i的最大值，即为答案。

四、代码实现：C++版高效解法

结合上述思路，我们编写C++代码，核心要点：

无需显式构建+1/-1序列和前缀和数组，用一个变量count实时计算前缀和，节省空间；
哈希表first_pos记录每个前缀和值第一次出现的下标，初始化first_pos[0] = -1（对应前缀和S[0]=0的下标）；
遍历过程中，实时更新最长良好时段的长度ans；
利用前缀和的连续性，仅需判断count-1是否存在，即可快速找到满足条件的前驱值。

完整C++代码

#include<iostream>#include<vector>#include<unordered_map>#include<algorithm>usingnamespacestd;// 求解最长良好时段intlongestWPI(vector<int>&hours){intn=hours.size();unordered_map<int,int>first_pos;// 记录前缀和第一次出现的下标intcount=0;// 实时计算前缀和，替代显式的前缀和数组intans=0;// 记录最长良好时段长度first_pos[0]=-1;// 初始化：前缀和0出现在下标-1（哨兵值）for(inti=0;i<n;++i){// 转化为+1/-1，更新实时前缀和count+=(hours[i]>8)?1:-1;// 记录当前前缀和第一次出现的下标（只记录第一次，保证i尽可能小）if(first_pos.find(count)==first_pos.end()){first_pos[count]=i;}// 寻找count-1（利用前缀和连续性，小于count的第一个值）if(first_pos.find(count-1)!=first_pos.end()){ans=max(ans,i-first_pos[count-1]);}}returnans;}// 测试案例intmain(){vector<int>hours={9,9,6,0,6,6,9};// 对应题目中的9960669cout<<"最长良好时段长度："<<longestWPI(hours)<<endl;// 输出3return0;}

代码逐行讲解

变量初始化：
- first_pos：哈希表，键为前缀和值，值为该值第一次出现的下标；
- count：实时前缀和，替代显式构建前缀和数组，空间复杂度从O ( n ) O(n)O(n)降至O ( 1 ) O(1)O(1)；
- first_pos[0] = -1：初始化哨兵值，对应前缀和S [ 0 ] = 0 S[0]=0S[0]=0，处理边界情况（如从序列第一个元素开始的良好时段）。
遍历原数组：
- 对每个元素hours[i]，大于8则count+1（良好），否则count-1（不良），完成+1/-1转化和前缀和实时计算；
- 若当前count未在first_pos中出现过，记录其下标i——只记录第一次，保证后续找到的前驱下标尽可能小，区间长度尽可能大。
寻找满足条件的前驱值：
- 利用前缀和的连续性，只需判断count-1是否存在（小于count的第一个值）；
- 若存在，计算当前下标i与count-1第一次出现的下标之差，更新ans为最大值。
测试案例：
- 输入{9,9,6,0,6,6,9}，对应转化后的+1/-1序列[1,1,-1,-1,-1,-1,1]；
- 最终输出3，即最长良好时段为前3个元素[9,9,6]（良好2次，不良1次，2>1）。