滑动窗口将x减到0的最小操作数这道题我前前后后刷了四遍每次重看一遍都有新的理解。LeetCode上编号1658题面一句话就能读完给一个整数数组和一个整数x每次操作可以从数组最左侧或者最右侧移除一个元素同时把x减去这个元素的值求最少多少次操作能让x恰好减到0做不到就返回-1。就是这句话里“从左右两端取数”这个动作最容易把人带进死胡同我第一遍刷的时候就在这卡了快两个小时。这篇不说空话直接把这道题为什么难、为什么能转化成滑动窗口、代码怎么写、有哪些必须注意的边界一次性拆干净。适合三类人看刚开始刷算法题、对滑动窗口思想总是一知半解的准备面试、想把这题答出深度的已经刷过一遍但总觉得哪里没想透、想补底层逻辑的。1. 真正让思路卡住的地方不是代码是“从两端取数”这个动作本身1.1 第一直觉为什么总往DP和贪心上跑拿到这道题第一反应几乎都是每次有左右两个选择那我递归地试不就好了定义一个dfs(l, r, rest)表示当前数组剩下从l到r这一段还需要减掉rest每次递归就尝试拿走nums[l]或者nums[r]。这个方向看起来无比自然但算一下就凉了数组长度最多是10^5状态规模是O(n^2)每个状态还有两个分支直接指数爆炸跑都跑不动。那换个思路贪心行不行每次选更大的那个数拿操作数不就更少吗拿两组数据试试就露馅了。比如nums [1, 1, 1, 1, 100, 1]x 102。贪心会先拿100然后左右两端都是1再拿两个1再补一个1一共4次看着好像没问题。但如果换成nums [3, 2, 20, 1, 1, 3]x 10贪心先拿3再拿3接着拿1和1剩中间一个20左边还有2拿不了凑不够10直接失败。可实际上最优解只需要5次先拿左边3和2再拿右边3、1、1恰好等于10。贪心在“局部最优”上就错了因为左右两侧的数凑成x的组合是全局的不是单看某一步大小能决定的。这也是很多题解上来就讲滑动窗口读者却觉得突兀的原因从“两端拿数”到“中间连续子数组”中间隔着一整层思维转换这层不补上代码看懂了也记不住。1.2 “同时从两边拿”会让思考维度爆炸如果一直盯着“被拿走的数”问题就是一个二维的动态过程左侧拿走几个、右侧拿走几个两个方向的取舍互相影响。左侧多拿一个右侧就得少凑一点这种牵一发动全身的关系没有任何简单的递推规则能覆盖。但换个观察角度把目光从“拿走的”转到“剩下的”上事情立刻简化。不管左侧拿走几个、右侧拿走几个数组中间没被拿走的那些元素一定是原来数组中连续的一段。这个“连续”是整道题最大的突破口。高中数学里有一种常用的换元思想一个复杂条件不好直接处理就把它等价地翻译成另一个条件。这里就是把“移除的元素和等于x”翻译成“剩余的元素和等于总和减x”。一旦翻译过来问题就从“从外部向内部收敛”变成了“在内部找一个固定和的连续段”复杂度直接从指数级掉到线性级。1.3 给零基础读者补一个“连续子数组”的直觉连续子数组通俗说就是数组中紧挨着的一段比如[3, 2, 20]是[3, 2, 20, 1, 1, 3]的一个连续子数组但[3, 20, 1]不是因为中间隔着2。滑动窗口的所有操作都是在这种“紧挨着的一段”上进行的。可以这样想象一队人排队检票队伍是一整排检票口只能覆盖其中连续的一段人。队伍往前走一步窗口右边界就多覆盖一个人窗口左边界就少覆盖一个人窗口里始终是连续的一段。滑动窗口算法就是这个“队伍往前移动窗口跟着滑动”的过程。后面所有代码本质上都是在控制这个窗口的两个边界。2. 核心转化把“x减到0”翻译成“找一个定和的最长连续段”2.1 公式推导到底在推什么设数组总和为total sum(nums)。假设最终的合法操作里左边移走了若干个元素右边移走了若干个元素移走的所有元素之和等于x。那么剩下来的就是中间连续的一段设它的和为windowSum。显然total windowSum x移项得到windowSum total - x把这个固定值记为target。于是原问题变成在数组里找一段连续子数组让它的和恰好等于target并且这一段越长越好。最终答案就是n - 最长连续段长度。因为移除的个数越少剩余的这一段就越长反过来找到一个“最长的合法剩余段”就用总长度减去它得到的就是最少移除次数。这就是这道题的核心换元。网上很多讨论把这一步叫“反向思维”或“补集思想”本质都是同一件事把对移除元素的求解转成对剩余元素的求解。2.2 两个必须在写代码前处理的特判在正式进入滑动窗口之前有两个边界条件一定要先处理不然后面代码很容易出幺蛾子。如果total x所有元素加起来都不够x减那直接返回-1没有任何操作序列能满足要求。如果total x说明必须把所有元素全部移走答案就是n。这两个特判不只是省时间更重要的是防止target变成负数。想想看一旦total xtarget total - x就是负数而滑动窗口维护的是一个“窗口内元素和”的概念数组里全是正整数窗口和永远不可能等于负数代码会在各种奇怪的比较中迷失方向。total x的情况同样值得单独处理虽然在某些巧合下算法也能算出正确答案但逻辑上就变得依赖“恰好碰上”不可控也不可读。2.3 为什么目标是“最长”不是“最短”这里有个特别容易绕晕的地方。原问题要求“最少操作数”翻译之后却要去求“最长连续子数组”这不是矛盾吗不矛盾。因为每一次操作移走一个元素移走的元素越少操作数自然越少。移走的元素少等价于剩下的元素多等价于剩余连续段长。所以“最少操作数”和“最长剩余段”是对偶的一个问题的两面。打个比方你要从一摞书的两侧各抽走几本要求抽走的总页数恰好等于某个数。抽走的本数越少越好那自然就是“尽量多留几本在中间不动”。留得越多动的越少。这个“留”的视角比“抽”的视角直观太多了。面试时如果能把这一步说清楚比直接默写代码加分得多。3. 滑动窗口能在这题成立靠的是“全正数”带来的单调性3.1 单调性为什么是滑动窗口的命根子LeetCode原题有一个约束容易被一眼扫过nums[i] 1数组里每个元素都是正整数。正是这个约束决定了滑动窗口可以成立。因为所有数为正所以当右边界向右扩展时窗口内元素和一定变大当左边界向右收缩时窗口内元素和一定变小。这个“只增不减、只减不增”的性质叫作单调性。有了它我们才能放心地使用“大了就缩左边界小了就扩右边界”这种简单策略。如果数组里混入负数或者0单调性就崩了窗口扩大一格和反而可能变小窗口缩小一格和反而可能变大。那时候滑动窗口的双指针移动就没有规律可循必须换成其他方案。这一点就是整道题能不能用滑动窗口的“资格证”。3.2 和“前缀和哈希表”方案放一起看才能看出优劣这道题也能用“前缀和哈希表”做。思路是先把前缀和数组prefix[i]算出来表示前i个元素的和然后遍历每个位置在哈希表里查一下prefix[i] - target是否出现过出现过就说明有一段连续子数组的和等于target。时间复杂度同样是O(n)但空间复杂度是O(n)因为要额外存一个哈希表。两种方案摆在一起看就很有意思对比项滑动窗口前缀和 哈希表时间复杂度O(n)O(n)空间复杂度O(1)O(n)对数组元素的要求必须全部为正数元素可为负、可为0代码复杂度简单、直观稍绕但通用面试推荐度本题首选作为延伸方案展示深度做题时应该优先选择滑动窗口因为它更快更省空间而且代码逻辑简洁。但面试官如果追问“数组里有负数怎么办”能立刻切换到前缀和哈希表并讲清楚原因会是非常亮眼的加分表现。我面试别人时最怕听到候选人只会背一种解法问他“换个数据特征还成立吗”就沉默。3.3 窗口维护的三条规则窗口的维护逻辑可以压缩成三个动作写代码前先在纸上理清楚右指针right从0开始向右遍历每到一个位置就把nums[right]加进当前窗口和windowSum。只要windowSum target就不断把左指针nums[left]从窗口和里减掉同时left右移。这一步是“收缩”目的是让窗口和降到不超过target。收缩完之后如果windowSum target说明当前窗口就是一个合法候选记录它的长度right - left 1并更新全局最大长度。这里要特别强调一个顺序问题必须先收缩、再判断是否相等。如果反过来先判断相等再收缩很可能在窗口和还大于target的时候就贸然记录一个非法状态答案就错了。很多初学滑动窗口的人在这里栽跟头代码看着逻辑没错跑测试用例却怎么都不对多半就是顺序搞反了。3.4 为什么收缩用while不用if右指针一次右移可能让窗口和瞬间增加很多。比如target是5当前窗口和是3右指针加进来一个值为10的元素窗口和变成13这时只收缩一个左元素根本降不到5以下可能要连续收缩好几次。所以收缩必须写成一个while循环直到窗口和小于等于target为止。有人担心这样会不会导致整体复杂度变成O(n^2)。不会。因为左指针left在整个遍历过程中只向右移动每个元素最多被“移出窗口”一次。右指针移动n次左指针累计也最多移动n次均摊下来还是O(n)。这就是滑动窗口最优雅的地方每个元素进窗口一次、出窗口一次总操作量是线性的。4. 完整实现与三版代码对比4.1 Python参考实现直接上我调试过多遍的Python版本from typing import List class Solution: def minOperations(self, nums: List[int], x: int) - int: n len(nums) total sum(nums) # 边界情况总和不满足要求 if total x: return -1 if total x: return n target total - x left 0 window_sum 0 max_len 0 for right, val in enumerate(nums): window_sum val # 窗口和超过 target 时不断收缩左边 while left right and window_sum target: window_sum - nums[left] left 1 # 收缩完再判断是否恰好相等 if window_sum target: max_len max(max_len, right - left 1) # 找不到任何和为 target 的连续子数组 if max_len 0: return -1 return n - max_len这段代码有几个细节值得停下来看。第一个细节是max_len初始化为0同时target不为0的情况已经保证窗口不可能为空所以最后max_len 0可以直接用来判断“无解”。如果target不是0但数组里根本不存在一段和为target的连续子数组max_len就会一直停留在0返回-1正好符合题意。第二个细节是while left right这个条件。当target非常小的时候虽然本题里target0左指针可能会一直右移直到越过右指针如果不加left right的保护下一轮循环访问nums[left]就会越界。很多精简版题解不写这个条件是因为他们依赖“正整数”保证循环会自然停下但代码的健壮性角度写上更稳妥。第三个细节是答案更新时机。我在while循环之后才判断window_sum target也就是窗口已经收缩到“和不超过target”的状态。此时如果相等说明这是一个真实有效的候选如果不等说明窗口和还小于target需要继续扩展右边界此时记录窗口长度为时过早。4.2 Java实现Java版本逻辑一模一样只是语法不同class Solution { public int minOperations(int[] nums, int x) { int n nums.length; int total 0; for (int num : nums) { total num; } if (total x) return -1; if (total x) return n; int target total - x; int left 0; int windowSum 0; int maxLen 0; for (int right 0; right n; right) { windowSum nums[right]; while (left right windowSum target) { windowSum - nums[left]; left; } if (windowSum target) { maxLen Math.max(maxLen, right - left 1); } } return maxLen 0 ? -1 : n - maxLen; } }Java版有两点小提醒一是习惯上可以用long来存总和虽然本题约束下int够用但养成用long的习惯可以避免一些边界数据溢出二是Math.max比手写三元表达式更清晰但两者性能没有区别纯风格问题。4.3 测试用例对照表写完代码动手跑几个用例比只看逻辑更踏实。下面是我本地验证过的一组用例覆盖了各种典型情况输入numsxtotaltarget最长合法连续段输出[1,1,4,2,3]5116[1,1,4]长度32[5,6,7,8,9]43531不存在-1[3,2,20,1,1,3]103020[20]长度15[1,2,3,4,5]15150全部保留5[1,1]32-1无需进入-1第一个用例最有意思它对应着从右侧拿两次的解法。数组[1,1,4,2,3]x5最优操作是从右边拿掉2和3总共2次中间剩下[1,1,4]这段和为6的子数组。滑动窗口找到的最长合法段长度是3用5减去3得到2完美对应。第五个用例则展示了total x时直接返回-1的防御逻辑根本不需要进入滑动窗口主流程。5. 四刷之后我总结出的几个“必踩坑”5.1 坑一漏掉total x的特判靠巧合拿到正确答案我第一次写的时候没处理total x心想反正进滑动窗口也能算出来。测试用例一跑居然对了但仔细分析才发现是碰巧当target等于0时数组里又全是正整数任何非空窗口和都大于0window_sum target永远不会成立max_len保持0最后n - 0 n结果恰好也是n。逻辑上看着对但完全是阴差阳错。更隐蔽的问题在于如果题目将来扩展成允许nums[i] 0这个巧合就彻底碎了某个空窗口或者和等于0的子数组会被错误记录答案直接错乱。所以这个特判必须写它保证的是逻辑自洽不是省那几行代码。5.2 坑二while循环不写left right数组越界当target很小而nums[left]又很大的时候收缩循环可能一口气把left推到right的右边。例如数组[9, 1]target 1right0时窗口和9收缩一次left变1leftright窗口内还有一个元素1如果target更小比如target0虽然被特判拦住了但防御性编程总得想循环就会继续收缩到left2越过right下一次循环再访问nums[left]就是越界。虽然本题有target 0且元素全为正数的保护left最多等于right而不会越过但写成while (left right windowSum target)是零成本的防御习惯可以避免未来改代码时埋雷。5.3 坑三更新答案的时机不对记录到非法窗口长度我见过很多人把代码写成这样if window_sum target: max_len max(max_len, right - left 1) while window_sum target: window_sum - nums[left] left 1先判断相等再收缩。这个写法的问题在于如果右指针刚扩展完窗口和已经超过了target程序应该先收缩再看收缩后的状态是否恰好等于target。把判断放在收缩前等于用一个“不合格的窗口”去更新答案记录到的长度毫无意义。这个坑特别隐蔽因为当窗口和恰好等于target时两种写法结果一样只有窗口超了target时才会暴露。而测试用例往往选那些“刚好命中”的例子导致错误被掩盖直到跑大量随机数据才现原形。正确写法永远是“先收缩到不超过target再判断是否相等”。5.4 坑四以为双指针就是“从数组两端同时往中间走”这个坑属于方法论层面。看到“最左侧”“最右侧”两个词第一反应就是设两个指针从两端往中间夹。但这个方向是错的如果两个指针都从两端往中间走它们之间剩下的部分虽然也是连续段但两个指针移动的次数互相制约状态组合爆炸没有任何单调规律可循。正确的双指针应该是“固定中间要保留的那一段左右边界都朝右移动”这就是滑动窗口。关键区别在于数组两端的删除是动态的、可多可少的而窗口的左右边界是明确从0开始、都向右推进的每一步的决策空间只有“扩右”和“缩左”两种配合单调性就能O(n)解决。这个思维的转变比记住任何代码模板都重要。5.5 坑五以为“最短窗口”才是目标把逻辑彻底搞反有一类题确实求最短窗口比如“满足某条件的最短子数组”这题却是求最长窗口。原因前面已经说过剩余越长操作越少。我第二遍刷的时候直接套了最短窗口模板写出了反逻辑的代码样例都能过一到隐藏样例就挂调了半天才意识到目标方向反了。滑动窗口模板本身不复杂但每道题“最长”还是“最短”必须从问题定义出发推一遍不能凭感觉套。6. 从这道题延伸出去的几个变体值得一起想通6.1 如果数组元素可以为0或负数滑动窗口立刻失效。原因还是单调性负数会让窗口扩大时和反而变小无法用“大了缩、小了扩”的规则收敛。此时改成前缀和哈希表的方案用哈希表记录每个前缀和第一次出现的位置遍历时查prefix[i] - target是否已存在存在则说明区间和为target。这个方案时间复杂度不变空间换稳定性。6.2 如果题目改成“必须从两端交替取”那就引入了“上一次从哪边取”的状态普通滑动窗口直接失效需要用带状态的动态规划dp[l][r][last]表示剩余区间为[l, r]且上一次是左/右取时的最少次数。这类变题明显更难但面试中出现的概率不高。知道“题目一变形算法就要跟着变”这件事比会解变题本身更有价值。6.3 如果x特别小还能怎么优化当x远小于数组总和时我们关心的只是数组两端附近的一小段区域中间大部分元素永远不会被移除。这时可以用两段枚举的思路先从左侧枚举取k个元素的所有组合再从右侧枚举用x - 左侧和来凑配合哈希表可以避免遍历整个数组。这种优化思路在实际工程里也很常见数据量太大时总是先分析“真正影响答案的范围在哪里”缩小搜索域后再动手。6.4 滑动窗口的通用识别信号刷多了会发现滑动窗口类题目通常有三个信号操作对象是一段连续的区域子数组、子串、连续k个元素数据具备某种单调性全正数、全负数、有序数组等目标是在满足某个约束下求最大或最小长度或者窗口内统计某种累计值。看到这三个信号同时出现滑动窗口大概率是正解。反过来如果数据不单调或者目标不是“连续段”再套滑动窗口就是刻舟求剑了。7. 写在四刷之后的体会第四次刷完这道题我最深的感受是大多数人不是不会写滑动窗口的代码而是卡在“为什么这道题能用滑动窗口”的推导上。从“左右拿数”到“中间留段”从“最小操作数”到“最长连续子数组”这两步换元没有神奇的技巧只是一点一点从题面条件里抠出来的。我后来给自己定了一个小规矩做题时不在代码注释里直接写“滑动窗口模板”而是写上“target total - x找最长连续段”这样每次重看都能快速想起当时的推导链路而不是背一段和自己无关的模板。你现在如果也被这道题绕得头疼别急着看答案先拿纸笔写写“剩下的数之和是多少”“它对应哪一段”“这段能有多长”大概率写到这里眼前就亮了。