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

解锁最长良好时段问题前缀和哈希表的优雅解法lBilibili 同步视频一、问题溯源读懂最长良好时段的核心要求问题初转化把次数比较变成数值运算二、核心原理前缀和——快速计算区间和的利器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]0S [ i ] S[i]S[i]表示序列A AA的前i ii项和即S [ 0 ] 0 S[0] 0S[0]0S [ 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]\dotsA[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[r1] - S[l]sum(A[l..r])S[r1]−S[l]原理图解原数组A[A0, A1, A2, A3, A4] 前缀和S[0, S1, S2, S3, S4, S5] 求A[1..3]的和A1A2A3 (A0A1A2A3) - A0 S4 - S1从图中能清晰看到区间[ l , r ] [l,r][l,r]的和等于前缀和数组中“后点减前点”这一特性让我们摆脱了对原数组的重复遍历。3. 问题二次转化前缀和数组上的新问题结合前缀和的区间和公式原问题“找A AA中sum0的最长连续子区间[ l , r ] [l,r][l,r]”可以转化为S [ r 1 ] − S [ l ] 0 ⟹ S [ r 1 ] S [ l ] S[r1] - S[l] 0 \implies S[r1] S[l]S[r1]−S[l]0⟹S[r1]S[l]同时子区间[ l , r ] [l,r][l,r]的长度为r − l 1 ( r 1 ) − l r-l1 (r1) - lr−l1(r1)−l。因此原问题最终转化为在前缀和数组S SS中找到两个下标i ii和j jjj i jiji满足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 ijij满足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代码#includeiostream#includevector#includeunordered_map#includealgorithmusingnamespacestd;// 求解最长良好时段intlongestWPI(vectorinthours){intnhours.size();unordered_mapint,intfirst_pos;// 记录前缀和第一次出现的下标intcount0;// 实时计算前缀和替代显式的前缀和数组intans0;// 记录最长良好时段长度first_pos[0]-1;// 初始化前缀和0出现在下标-1哨兵值for(inti0;in;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()){ansmax(ans,i-first_pos[count-1]);}}returnans;}// 测试案例intmain(){vectorinthours{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则count1良好否则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次21。算法性能分析时间复杂度O ( n ) O(n)O(n)仅对原数组进行一次遍历哈希表的查找和插入操作均为O ( 1 ) O(1)O(1)平均情况空间复杂度O ( n ) O(n)O(n)最坏情况下前缀和的每个值都不重复哈希表需要存储n 1 n1n1个键值对相比暴力枚举所有区间的O ( n 2 ) O(n^2)O(n2)时间复杂度该解法实现了质的提升能高效处理大规模数组。五、拓展思考算法的灵活变通本文的解法基于“前缀和哈希表”并利用了“原序列只有1/-1前缀和连续”的特性做了优化让代码更简洁。但这一思路可以推广到更通用的场景如果原问题的“良好/不良”转化后不是1/-1而是任意整数那么只需去掉对count-1的判断改为遍历哈希表中所有小于当前count的值即可找到满足条件的前驱下标。当然此时时间复杂度会略有上升但核心思路前缀和哈希表记录第一次出现位置依然适用。此外该问题与LeetCode 1124. 表现良好的最长时间段完全一致本文的解法可以直接解决该题大家可以动手测试更多案例。六、总结最长良好时段问题的解题过程是一次典型的算法问题转化训练从“次数比较”到“1/-1序列”再到“前缀和数组的差值比较”每一步转化都让问题向经典算法靠拢。而前缀和哈希表的组合更是处理数组区间和问题的黄金搭档掌握这一组合能解决一大类类似的算法题。解题的关键从来不是死记硬背代码而是理解为什么要转化、为什么用这个数据结构转化是为了将未知问题变为已知问题前缀和是为了快速计算区间和哈希表是为了快速找到满足条件的前驱下标保证区间长度最大。希望这篇文章能让你对前缀和技巧有更深入的理解在算法刷题的路上更上一层楼