1. 为什么这两道题总被一起提起名字像解法却完全相反如果你刷过LeetCode热门100题大概率会注意到一个有意思的组合——和为K的子数组和滑动窗口的最大值经常出现在同一份刷题清单里甚至在同一天的计划中。我第一次刷到这两题时的第一反应是都是子数组问题都跟连续区间有关那解法思路应该差不多吧结果做下来才发现这两题看似名字极像核心思路却几乎完全相反。一个要靠前缀和与哈希表来绕过暴力枚举一个要靠单调队列来淘汰无用元素。把它们放在一起对比着学反而能一次性搞懂LeetCode里两类最高频的区间类题型的底层逻辑。先说个小背景。这两题分别是LeetCode 560和为K的子数组和LeetCode 239滑动窗口最大值。前者是前缀和哈希表的经典代表后者是单调队列的经典代表。在面试中出现频率都极高美团、字节、微软都爱考。尤其是和为K的子数组它还有一个特别容易踩的坑很多人上手就写滑动窗口结果发现窗口缩不动。为什么会这样后面我会专门拆这个问题。这篇文章不谈虚的直接以两题为核心把暴力解、优化解、常见误区、面试追问全部过一遍。你要是正在准备面试、刷Hot 100或者想搞懂这两类题型的底层模式这篇应该能省你不少时间。2. 和为K的子数组核心是前缀和与哈希表的配合2.1 先用暴力法感受题目的尺度先看题目给你一个整数数组nums和一个整数k要求统计并返回该数组中和为k的连续子数组的个数。注意题目没有说数组元素一定是正数这一点极其关键。最直观的暴力做法是把所有连续子数组枚举一遍。怎么枚举固定左端点i向右扩展右端点j同时累加nums[i]到nums[j]的和。如果累加和等于k计数加1。代码大概长这样def subarraySum(nums, k): n len(nums) count 0 for i in range(n): total 0 for j in range(i, n): total nums[j] if total k: count 1 return count这段代码的时间复杂度是O(n^2)。听起来好像也不差LeetCode上n的规模上限是2万O(n^2)意味着最坏要跑4亿次循环。Python环境下大概率超时C也悬。所以必须优化。这里我先强调一个容易被忽略的点暴力法本身也有价值。它的价值不在于能AC而在于帮我们确立什么是正确答案的参照系。后面优化完你可以用暴力法跑随机样例来对拍确保优化结果没错。这是实战中非常重要的习惯很多人一上来就写优化代码写完心里没底其实先用暴力法打个底是最稳的。2.2 前缀和把区间和变成两个前缀和的差说句实话我第一次看到前缀和这个技巧时觉得它就是数学上的移项变换没什么了不起。但后来刷题多了才发现前缀和的价值在于把连续子数组求和这个看起来需要枚举的操作变成了一次O(1)的减法。做法是先预处理出一个前缀和数组pre其中pre[i]表示nums[0]到nums[i-1]的和pre[0] 0。那么nums[i]到nums[j]的区间和就等于pre[j1] - pre[i]。这个结论很简单但它直接改变了问题的形态原来的问题找有多少对(i, j)使得nums[i] ... nums[j] k。 变换后的问题找有多少对(i, j)使得pre[j1] - pre[i] k。再移项一下pre[i] pre[j1] - k。这一步变换出来问题就从一个区间求和问题变成了一个找差值问题。而找差值天然可以用哈希表来加速。2.3 哈希表优化从O(n^2)到O(n)的临门一脚现在我们要遍历前缀和数组。假设当前遍历到pre[j1]也就是扫描到原数组下标j我们想知道在它之前有多少个前缀和的值恰好等于pre[j1] - k如果这个值出现了m次那就说明有m个起点对应的连续子数组的和为k。这里用哈希表来记录某个前缀和出现过多少次就能在常数时间内完成查询。代码实现如下def subarraySum(nums, k): count 0 pre_sum 0 # 哈希表初始化前缀和为0出现一次表示从头开始的前缀 hash_map {0: 1} for num in nums: pre_sum num # 这里查的是在此之前出现过的前缀和 diff pre_sum - k if diff in hash_map: count hash_map[diff] # 更新当前前缀和的出现次数 hash_map[pre_sum] hash_map.get(pre_sum, 0) 1 return count细节上说几个点。第一hash_map初始要有{0: 1}。因为前缀和为0意味着区间的起点就是数组下标0没有这个初始值从头开始的合法子数组会被漏掉。举个例子nums [1, 2, 3], k 3正确答案有两个子数组[3]和[1, 2]。如果哈希表初始为空则扫描完3时查不到pre_sum - k 3 - 3 0这个历史前缀和答案少一个。所以{0: 1}这个初始化是所有教程都会强调的根本原因。第二为什么先查diff再更新当前pre_sum因为题目要求子数组连续且非空起点必须在终点之前。如果先更新当前前缀和的计数再查询就会把[当前元素本身]这种长度为0的区间也算进去导致答案错误。这里顺序不能反。第三时间复杂度是O(n)空间复杂度也是O(n)。在哈希表里存的每个前缀和在后续扫描中都有可能被查询到所以需要全部保留没有节省空间的余地。2.4 为什么这道题不能用滑动窗口负数的存在打破了窗口的单调性这是和为K的子数组最大的一个坑我见过太多次了。很多人在看到连续子数组、和为K之后第一反应是这不就是滑动窗口的活儿吗右指针右移扩大窗口和左指针右移缩小窗口和追到等于K计数。但这套逻辑成立的前提是窗口和随着右指针右移单调递增或者说窗口收缩时和必然减小。只有当数组元素全部非负时右扩窗口和才只增不减左缩窗口才只减不增。而560题并没有说数组全是正数。一旦数组里有负数右指针右移窗口和可能变小左指针左移窗口和可能变大两个指针都失去了该往哪边动的依据。举个例子nums [-1, -1, 1], k 0。假设窗口从[-1]开始右移变成[-1, -1]和是-2小于0。这时如果把左指针右移丢掉第一个-1窗口变成[-1]和是-1又不对。但正确答案其实是[-1, 1]这个区间它需要右指针先跨过两个负数到下标2和变成-1再把左指针跨过一个-1和变成0。整个过程里窗口和不是单调变化的滑动窗口根本没法判断什么时候该扩张、什么时候该收缩。所以记住一个结论含负数的连续子数组求和类问题优先考虑前缀和哈希表元素全非负时才考虑滑动窗口。这个判断标准非常实用后面我还会把它扩展成一张判断框架表。3. 滑动窗口的最大值单调队列才是解题灵魂3.1 为什么最大值不能像和那样跟着窗口移动更新再来看239题给定数组nums和窗口大小k窗口每次向右滑动一位要求输出每个窗口的最大值。最容易想到的暴力做法是每次窗口移动时遍历窗口内k个元素找最大值总复杂度O(nk)。数据规模大的时候肯定不行。有人会想既然窗口每次只移动一格那我是不是可以维护一个变量记录当前窗口最大值移动时对比新进来的元素就行这样在窗口扩张阶段确实够用但窗口还会左端收缩——被移出窗口的那个元素可能就是当前最大值。比如窗口[3, 1, 2]最大值为3窗口右移变成[1, 2, 4]移出去的是3新进来的是4最大值变成4更新起来很简单。但如果移出去的是3新进来的是1窗口变成[1, 2, 1]最大值变成2而2是窗口里的老二。这时候只靠最大值变量就没法知道老二到底是谁必须重新扫描窗口。所以问题的关键不是如何快速求新窗口的最大值而是**如何在被移除掉当前最大值之后快速找到窗口内的下一个最大值**。这个需求恰好是单调队列能解决的。3.2 单调队列的核心思想窗口退化成了递减队列单调队列的思路是用一个双端队列deque来维护窗口内元素的索引同时保证这些索引对应的数值从队头到队尾是严格递减的。也就是说队头永远是当前窗口最大值的索引。怎么维护这个递减性质窗口右移时做两件事第一新元素入队前把队列尾部所有比它小的元素全部弹出。为什么可以弹因为那些元素比新元素小而且它们在窗口中的位置比新元素靠左意味着它们会早于新元素离开窗口。也就是说只要新元素还在窗口里那些更小、更早的元素就永远没有机会成为窗口最大值。它们留在队列里只会碍事直接弹掉。第二队头如果已经滑出窗口左边界也要弹出。也就是说每次移动后先检查队头索引是否小于等于i - k如果是就popleft()。这个思路第一次接触时有点绕我建议用一个具体例子手推一遍。假设nums [1, 3, -1, -3, 5, 3, 6, 7], k 3我们来走前几步i0元素1队列空直接把索引0入队。队列[0]i1元素3队尾元素1比3小弹出索引1入队。队列[1]i2元素-1队尾索引1对应数组值3不小于-1不弹索引2入队。队列[1, 2]。窗口[0,2]队头索引1对应值3最大值是3。i3元素-3队尾索引2对应值-1不小于-3不弹索引3入队。队列[1,2,3]。此时窗口范围[1,3]队头索引1仍在窗口内最大值3。i4元素5比队尾的-3、-1、3都大全部弹出索引4入队。队列[4]。窗口最大值5。你可以看到队列里元素数量在整个过程中远小于窗口大小因为它把永远不可能当最大值的元素提前淘汰了。这就是单调二字的意义队列内部呈现单调递减的数值排列而队头始终给出答案。3.3 完整代码与复杂度总结代码用Python的collections.deque来实现因为双端队列在两头增删都是O(1)from collections import deque def maxSlidingWindow(nums, k): n len(nums) if n 0: return [] res [] dq deque() # 存索引队头是窗口最大值的索引 for i in range(n): # 新元素入队前弹出队尾所有比它小的元素 while dq and nums[dq[-1]] nums[i]: dq.pop() dq.append(i) # 弹出已经滑出窗口的队头元素 if dq[0] i - k: dq.popleft() # 窗口完整时记录答案 if i k - 1: res.append(nums[dq[0]]) return res时间复杂度O(n)每个元素最多入队一次、出队一次均摊下来很干净。空间复杂度O(k)队列最坏情况下装下整个窗口。这里有个容易写错的小细节先维护单调性再弹出过期队头最后记录答案。顺序不能乱。如果把弹出过期队头放到了新元素入队之前会导致队头元素的索引可能已经过期但还没有被清理时新元素入队时比较大小可能会误用过期元素参与弹出判断虽然最终队头仍然正确但队列里可能残留无意义元素代码逻辑变混乱。按入队维护单调 → 清过期 → 记录的顺序来写不容易出错。3.4 面试官的追问最大值能换成最小值吗窗口尺寸可变呢这道题在面试里特别容易被追问。最经典的两个变体问题第一如果把最大值换成最小值怎么做思路完全一样只需要把队列改成单调递增即新元素入队前弹出所有比它大的元素队头就是窗口最小值。这个变体其实就是LeetCode 239的镜像理解了单调队列的本质改起来不超过三行。第二如果窗口大小不是固定的而是每个位置动态变化怎么办这个变体会引出另一类数据结构比如堆或者线段树但更常见的答案是对每个可能的窗口宽度预处理出结果——有一种做法叫稀疏表或分块RMQ能O(1)查询任意区间最值。如果面试问到这里通常是在考察你数据结构扩展能力能把单调队列讲清楚已经能拿不少印象分。4. 一题一法什么时候用滑动窗口什么时候用前缀和4.1 两张算法的能力边界对比刷题刷到一定量之后你会发现很多问题卡住的原因不是不会写代码而是不会选择算法。这里我整理了一张对比表是我在实际刷题和面试中反复用过的心法特征和为K的子数组560滑动窗口最大值239数组元素是否可为负可以这是核心难点可以为任意值无所谓要统计的目标满足和的子数组个数每个窗口的最大值序列核心数据结构前缀和数组 哈希表双端队列单调队列时间复杂度O(n)O(n)关键限制条件元素非负时才可用双指针/滑动窗口窗口大小固定常见变体和为K的最短/最长子数组、乘积小于K的子数组窗口最小值、窗口内第二大、双窗口另外我总结了一个更通用的决策口诀特别适合笔试时快速判断如果题目说连续子数组的和/乘积恰好等于某值且数组可能含负数 → 前缀和 哈希表。如果题目说连续子数组的和至少/至多为某值且数组全为正数 → 滑动窗口双指针。如果题目说每个固定大小窗口内求最值 → 单调队列。如果题目说多组不同窗口大小求最值 → 考虑单调队列配合预处理或者线段树。这个口诀解决了我80%以上的该用什么方法问题。剩下20%要靠题目中的变体条件灵活变通但大方向不会错。4.2 从输入规模反推算法复杂度还有一个很实用的经验用n的规模反推可接受的复杂度。比如数组长度是10^5量级那O(n^2)基本没戏能接受的通常是O(n)或O(n log n)。如果是10^3量级O(n^2)可以接受这时候直接写暴力法都行。在做1605这类知道要做优化但不确定优化到什么程度的题目时我通常先算几组数据的规模范围再决定要不要上哈希表或单调队列。这个方法不仅适用于这两题对所有算法题都适用。5. 从两道题延伸出去变形题的套路与应对5.1 和为K的子数组的三类高频变形变形一求和为K的最短连续子数组长度。这个只要在遍历前缀和时哈希表里记录前缀和第一次出现的位置因为我们要最短所以保留最早出现的索引。变形二求乘积小于K的子数组个数。乘积和加法最大的区别在于乘积会随元素增大而膨胀而且元素为正数时具有单调性所以这题反而是用滑动窗口/双指针的正统场景。负数一旦出现乘积的符号会翻转情况就麻烦了。所以判断加法和乘法问题先看元素符号。变形三求和为K的子数组并且要求子数组连续且有序。这种题本质上还是哈希表只是查询时加了个索引在当前位置之前的前提跟原题的做法一致。还有一个LeetCode周赛里出现过的变体nums是循环数组。处理方法是把数组副本接在后面变成两倍长然后跑一遍和为K的代码但需要限制子数组长度不超过原数组长度。这类题的核心套路就是把循环数组拉直且记得控制窗口长度上限。5.2 滑动窗口最大值的两个高阶变体变体一窗口大小k本身也会变化。LeetCode 周赛430里有一道类似的题它不是固定窗口而是对每个位置求出以该位置为右端点窗口大小阈值内的最大值或最小值。这种题通常需要维护一个右端点固定的单调队列配合遍历顺序依次求解。变体二需要返回窗口内的第二大值或第k大值。单调队列只能高效维护最值维护第二大就力不从心了。这种情况有两个思路一是用堆加延迟删除维护TopK二是用线段树/树状数组动态维护窗口内数值频次。后者适合值域较小的情况前者更通用。坦白说这两个变体难度都不小但如果能先把239题的单调队列吃透再去碰变体题至少能理解为什么单纯维护最大值变量不够用以及为什么单调队列能保证均摊O(1)。这些理解比背代码重要得多。6. 我在实际刷题中的体会与建议最后聊几句个人的刷题体会。第一这两道题我建议一天之内连着刷而且按暴力 → 前缀和/单调队列推导 → 变形题的顺序来。先写暴力感知问题的规模再推导优化理解每一步操作的目的最后写变形检验是否真的理解了。第二非常重要的一点刷完别急着下一题把代码跑一遍随机测试数据。拿和为K的子数组来说我自己就吃过亏——哈希表初始值漏了{0: 1}小规模数据跑对了随机大测试一跑就错。后来养成了拿暴力版本对拍的习惯信心足了很多。239题也是一样边界情况如k1或kn都要手动测一遍。第三面试的时候如果遇到239题不要只闷头写代码。面试官其实更想听你解释为什么维护单调队列是正确的为什么可以放心pop掉队尾比当前元素小的元素把被弹出者再也没有机会成为窗口最大值这个论证讲清楚这道题基本就稳了。第四如果时间充裕建议把这两题的思想向其他题型迁移。比如说前缀和思想不仅在数组题里能用在二维矩阵里求子矩阵和也常用单调队列思想在股票价格、流式数据处理等场景里也经常出现。掌握的是思想而不只是代码后面刷题效率会高很多。这两道题看起来一个简单一个复杂但底层都在考察同一件事如何利用问题的单调性或结构性避免无效计算。前缀和避开的是重复的区间求和单调队列避开的是重复的全窗口扫描。你能套路化地识别出这类结构而不是死记模板才是刷Hot 100最有价值的收获。