将x减到0的最小操作数：一题吃透滑动窗口

我最初在力扣上刷到“将 x 减到 0 的最小操作数”这道题时以为它只是一道模拟题动手写了几版代码都被测试用例教做人。后来真正把思路理顺才发现这道题背后的滑动窗口解法非常经典它把一个看似需要“左右两端同时决策”的问题干净利落地翻译成了“找一段最长连续子数组”的问题。这篇文章就以这道题为例把滑动窗口从原理推导、代码实现到边界排查完整拆一遍。我也顺手把它整理成自己滑动窗口系列笔记的第 4 篇希望能给正在准备算法面试、或者刚接触滑动窗口想找个经典题练手的读者一点参考。1. 先看清楚题目从两端减 x到底在求什么1.1 题目描述还原原题大意是这样的给你一个整数数组 nums 和一个整数 x每一次操作你可以移除数组最左边或最右边的元素然后从 x 中减去这个元素的值。注意移除之后数组会发生变化后续操作只能基于剩下的数组继续。最终问能不能通过若干次操作让 x 恰好变成 0如果可以返回最小操作数如果不行返回 -1。从字面看这个规则很简单但真正动手时会发现难点在于“左右两端都能拿”而且拿的顺序不受限制。比如 nums [1,1,4,2,3]x 5直观上你可以先拿左边两个 1 得到 2再从右边拿一个 3总共 3 次操作但最优做法其实是把右边的 3 和 2 都拿掉x 刚好归零只需要 2 次操作。再比如 nums [3,2,20,1,1,3]x 10最左的两个数是 3 和 2最右的两个数是 1 和 3不管怎么组合最少也要 5 次操作。这类例子反复出现说明这道题没有简单的局部最优策略不能“哪边小拿哪边”也不能“哪边能凑够就拿哪边”。我们需要考虑的很可能是“左边取多少个、右边取多少个”的组合问题。换句话说这本质上不是一个模拟问题而是一个搜索和优化问题直接顺着题意去写代码很容易越写越偏。1.2 正向穷举会走进复杂度陷阱如果按照正向思路最暴力的做法就是枚举左边取 i 个元素、右边取 j 个元素i 加 j 就是操作数。只要两端取出来的元素之和等于 x就记录一次操作数最后取最小值。这个枚举量有多大左边界 i 有 O(n) 种可能右边界 j 也有 O(n) 种可能组合起来就是 O(n^2)。在力扣的测试规模下数组长度可以到 10^5O(n^2) 几乎注定超时。有人会说可以用前缀和把“两端取出的和”快速算出来把求和从 O(n) 降到 O(1)。这确实解决了快速求和的问题但组合本身依然是 O(n^2) 的只是把常数项缩小了而已。所以这道题真正要解决的并不是“怎么更快求和”而是“怎么减少枚举次数”。如果找不到一个办法把二维组合搜索降成一维扫描无论怎么优化局部计算都很难通过。这里还有一个容易踩的坑正向做的时候很多人会尝试维护左右两个指针然后根据当前拿走的总和与 x 的关系去调整。但“左边多拿一个”和“右边多拿一个”都会让拿走的总和变大两个自由度同时往一个方向变化你很难判断到底应该调整左指针还是右指针也没法保证当前的左右组合是最优的。这就是把问题困在二维搜索里的典型症状。1.3 关键一步把问题反过来看整个题目最精彩的部分在于一步逆向转化。你想每次都是从数组的最左边或最右边移除元素那么经过若干次操作之后数组中真正留下来的元素一定是最初数组里的一个连续子数组而且一定位于中间。左边被切掉一段右边被切掉一段剩下的就是一段中间的“夹心”。假设整个数组的总和是 total。如果最终 x 被减到 0说明被移除的元素总和正好等于 x。那么中间留下的那一段连续子数组的元素总和就应该是 total - x。我们希望操作次数最少也就是移除的元素个数最少反过来看就是希望中间留下的子数组长度最长。于是题目变成了这样一句话在 nums 中寻找一个最长的连续子数组使得它的和等于 total - x。找到之后答案就是数组长度减去这个最长子数组长度如果根本找不到这样的子数组就返回 -1。用生活里的例子类比一根总长度固定的绳子要从两端剪掉总长为 x 的一截剩下的就是中间一段。既然剪掉的长度已经固定想让剪的次数最少不如让中间保留的部分越长越好。这个逆向转化是理解整道题的关键也是这道题被称为“滑动窗口入门必刷题”的原因。想通了这一步后面写代码就只是顺水推舟。2. 滑动窗口在这里为什么是天然答案2.1 连续子数组问题与双指针的适配性“找一段连续子数组满足某个和条件”是滑动窗口最经典的适用场景。滑动窗口的核心思路是维护一个左边界 left 和右边界 right它们中间的部分就是当前窗口。右边界不断向右扩展当窗口内的条件不满足时左边界再向右收缩。整个过程像一扇可以伸缩的窗户在数组上从左往右扫一遍扫描结束答案也就出来了。这道题里数组元素都是正整数这给滑动窗口提供了一个非常好的性质窗口和 cur_sum 会随着 right 的右移而单调不减也会随着 left 的右移而单调不增。所以当 cur_sum 太大时只有收缩左边才有可能让它回到 target当 cur_sum 太小时只有扩展右边才有可能达到 target。两个指针的移动方向都是确定的不存在来回试探的困惑。正是因为这种单调性双指针才能在 O(n) 时间内完成搜索。我之前见过有人把滑动窗口理解成“左边缩一下、右边扩一下、左右交替调整”这是不对的。在标准滑动窗口里右指针始终只负责扩展左指针始终只负责收缩两个指针的行动逻辑完全不同。如果题目数组元素可能为负数窗口扩大不一定让和变大收缩也不一定让和变小这套单调性就崩了滑动窗口不能直接套用。这不是模板不好用而是问题性质发生了变化这点我在后文还会再提醒。2.2 target、窗口和、答案三者之间的关系刷题时最怕公式记混这道题的几个关键量我建议这样理解total整个数组的元素之和一上来就算好target total - x我们希望中间剩余子数组满足的目标和maxLen满足和为 target 的最长连续子数组长度最终答案 n - maxLen也就是最少需要移除的元素个数。我们手工走一遍示例 [1,1,4,2,3]x 5。total 11target 6。滑动窗口扫过数组时会发现 [1,1,4] 这一段的和正好是 6长度为 3并且没有任何比它更长的连续子数组和等于 6。于是 maxLen 3答案 5 - 3 2和题目预期一致。再看另一个示例 [3,2,20,1,1,3]x 10。total 30target 20。在这个数组里连续子数组和等于 20 的只有 [20] 这个长度为 1 的窗口所以 maxLen 1答案 6 - 1 5同样正确。这两个手算过程能让你直观感受到只要中间剩余部分算对最小操作数根本不用真的去模拟公式直接给出答案。需要特别强调的是我们找的是“最长”而不是“最短”的连续子数组。中间剩余越长说明两端移除的越少操作数自然越少。这个关系非常容易记反建议每做完一个示例都用公式验算一遍形成肌肉记忆。2.3 为什么不能直接两个指针从两端往中间走我知道一定会有读者提出一个看似更直观的解法左右各放一个指针左边指针往右走右边指针往左走两边同时往中间靠让两边取走的元素之和逼近 x。这个想法听起来很对称但实际操作时会发现左边指针右移和右边指针左移都会让“移除和”变大两个变量同时增加你根本判断不出当前该动哪一边也没法证明当前组合是不是最优的。更深层的原因是枚举左边取 i 个、右边取 j 个本质上是二维组合搜索复杂度很难降下来。而滑动窗口方案通过逆向转化把“中间剩余部分”看成一个窗口将问题压缩成了一维的“在数组里找一段和等于 target 的子数组”。这就把复杂度从 O(n^2) 降到了 O(n)。所以这道题的精髓不在窗口模板本身而在于那个把二维搜索压成一维扫描的逆向思路。想通这一层你才算真正会做这道题。3. 代码实现与边界条件全拆解3.1 三种常见语言的参考实现下面先给 Python 版本可读性最好。代码里我没有用任何高级语法方便直接搬到面试现场。def minOperations(nums, x): total sum(nums) if total x: return -1 if total x: return len(nums) target total - x left 0 cur_sum 0 max_len -1 for right in range(len(nums)): cur_sum nums[right] while cur_sum target: cur_sum - nums[left] left 1 if cur_sum target: max_len max(max_len, right - left 1) return -1 if max_len -1 else len(nums) - max_len再看 JavaScript 版本思路完全一致。如果你平时用 JS 刷题可以直接参考这份var minOperations function(nums, x) { const total nums.reduce((acc, val) acc val, 0); if (total x) return -1; if (total x) return nums.length; const target total - x; let left 0; let curSum 0; let maxLen -1; for (let right 0; right nums.length; right) { curSum nums[right]; while (curSum target) { curSum - nums[left]; left; } if (curSum target) { maxLen Math.max(maxLen, right - left 1); } } return maxLen -1 ? -1 : nums.length - maxLen; };C 版本也一起给出主要区别在类型和 accumulate 的用法核心逻辑没有变化int minOperations(vectorint nums, int x) { int total accumulate(nums.begin(), nums.end(), 0); if (total x) return -1; if (total x) return nums.size(); int target total - x; int left 0, curSum 0, maxLen -1; for (int right 0; right nums.size(); right) { curSum nums[right]; while (curSum target) { curSum - nums[left]; left; } if (curSum target) { maxLen max(maxLen, right - left 1); } } return maxLen -1 ? -1 : (int)nums.size() - maxLen; }3.2 窗口逻辑逐段解读先看外层 for 循环right 从 0 开始往右走每走一步就把 nums[right] 加进 cur_sum这等价于“尝试把右边界再扩大一格”。注意代码里没有真的修改原数组而是用 left 和 right 两个下标圈出一段范围窗口的扩展和收缩都只是重新计算 cur_sum。这个细节很重要如果谁在代码里真的去 splice 或删除了数组元素窗口下标会整个乱掉。再看内层 while 循环只要 cur_sum 大于 target说明当前窗口的和太大了而右边界已经走到当前最远的位置唯一能调整的方向就是让左边界往右收缩。每次收缩窗口长度减一cur_sum 减去 nums[left]left 自增。这里用 while 而不是 if是因为有可能需要连续收缩好几个元素才能把和降到 target 以下。收缩完之后cur_sum 一定小于等于 target。接下来是关键判断如果 cur_sum 恰好等于 target就用 right - left 1 更新最大长度。这里有一个初学者常问的问题为什么不在 while 之前判断因为如果 cur_sum 已经大于 target它不可能等于 target必须先收缩再判断如果 cur_sum 小于 target不需要收缩直接判断也不影响如果恰好等于 target则跳过 while直接进入 if。代码里的“先 while 后 if”顺序是安全且不遗漏的。还有一个容易忽略的细节就是 right - left 1 的含义。因为 left 和 right 都是下标窗口长度应该是右边界减左边界再加一而不是 right - left。这个 1 写漏的话结果会整体偏小而且很难通过小样例发现。3.3 三个必须先处理的边界条件第一个边界是 total x。如果整个数组加起来都不够 x无论怎么移除都不可能把 x 减到 0直接返回 -1。这个判断最容易被漏掉而一旦漏掉target 会变成负数后面的滑动窗口逻辑全部白跑。第二个边界是 total x。这意味着必须把数组所有元素全部移除操作数就是数组长度。为什么不能跳过这个特判因为此时 target 0滑动窗口要找的是和为 0 的空子数组。在 maxLen 初始化为 -1 的情况下代码不会把“空窗口”记入结果最后会返回 -1与正确答案 n 相悖。提前返回是最省心的处理方式。第三个边界是 maxLen 的初始值。很多人做“求最长子数组”时习惯把最大值初始化为 0但在这道题里maxLen 0 会被误认为“找到了长度为 0 的合法子数组”而实际上可能是“什么都没找到”。为了让“找不到窗口”和“窗口长度天然为 0”能区分开我把 maxLen 初始化为 -1最后返回时再做判断。当然如果你在开头处理了 total x 的特判用 0 做初始值也不是完全不行只是不够稳妥。另外补充一下 x 0 的情况。x 0 意味着不需要做任何操作最小操作数应该是 0。用我们的公式推一下target total - 0 total滑动窗口会在整个数组上找到和为 total 的子数组maxLen n答案 0代码可以正确处理。所以不需要额外特判但如果你希望在面试时表达得更清晰也可以在开头加一句 if (x 0) return 0。3.4 复杂度分析为什么 O(n) 就够很多读者看到 for 循环里套了一个 while第一反应是复杂度会不会变成 O(n^2)。我们来算一笔账内层 while 确实可能执行多次但 left 指针在整个过程中只会向右移动并且最多移动 n 次。也就是说每个元素最多被加入 cur_sum 一次最多被移除一次。整个算法的耗时与 n 成正比所以时间复杂度是 O(n)额外只用了几个变量空间复杂度是 O(1)。这也是滑动窗口能横扫一大类子数组问题的底气只要窗口的扩展和收缩条件维护得当就能在单次扫描里完成搜索。对比一下暴力枚举的 O(n^2)这个差距在 n 较大时是致命的。理解这里的复杂度推导也能帮你判断什么时候该用滑动窗口、什么时候该放弃。4. 实操中容易踩的坑与排查方法4.1 常见错误速查表我整理了一张表格把这道题以及同类滑动窗口题里最容易出的问题列在一起方便你自查。错误现象根本原因正确做法结果比正确答案多 1maxLen 初始化为 -1但找不到窗口时按 n - (-1) 计算找不到时单独返回 -1或配合 total x 特判total x 时没提前返回target 为负数窗口逻辑错乱目标值为负时不可能有合法窗口开头判断 total x直接返回 -1while 条件写成 cur_sum target等于 target 时也收缩错过合法窗口只有 cur_sum target 时才收缩收缩时忘了减 nums[left] 或 left 忘记自增窗口和计算错误两行代码缺一不可先减再加用 splice 或 del 直接删数组元素改变了原数组顺序窗口下标完全错乱永远用 left/right 两个下标描述窗口不真正删元素找最短子数组而不是最长子数组公式记反中间剩余越短反而移除越多反复用示例验算中间剩余越长操作数越少x 0 时误把答案算成 n没有识别“不需要操作”的语义可特判返回 0或验证公式能正确覆盖这张表里的前四行是我在实际刷题和帮人 review 代码时出现频率最高的四类问题。尤其是 while 条件写成 这个问题非常隐蔽因为在小数据量时偶尔能蒙对答案一旦遇到窗口和正好等于 target 的用例就直接错。4.2 一个真实的排查现场早期我写过一个版本把 while 条件误写成了 cur_sum target。结果在 target 6 的测试用例里窗口 [1,1,4] 的和刚好等于 6却被代码当成“过大”处理left 直接跳过第一个 1之后整个数组再也找不到和为 6 的窗口最终返回 -1。当时我盯着代码看了很久都没发现问题最后在循环里打印每一步的 left、right、cur_sum发现在 right 2 时 cur_sum 已经是 6代码却进入了收缩分支一下就定位到了症结。这个调试方法在滑动窗口题里特别通用在每个循环里打印 left、right 和当前窗口和绝大多数逻辑错误都会现出原形。如果结果只差一点点优先检查窗口长度的 1 是否写对如果结果完全错误优先检查 while 的判断条件。还有一个经验是提交之前最好自己跑三个用例一个标准示例、一个 total x 的用例、一个 x total 的用例。这三个用例分别覆盖了主逻辑、负向边界和全量移除边界能过滤掉大部分低级错误。4.3 由这道题延伸出的滑动窗口同类题一道题的价值在于让你掌握一类题的解法。滑动窗口在算法题里的变体非常多我列出几个常见方向无重复字符的最长子串窗口内维护字符集合扩大窗口直到出现重复字符再收缩左边界滑动窗口最大值窗口大小固定配合单调队列在 O(n) 内维护窗口最大值滑动窗口中位数窗口大小固定需要快速取中位数常见做法是双堆或有序容器最小覆盖子串窗口内的元素种类和数量作为约束用计数器判断是否满足覆盖条件。这些题都可以归到同一个抽象框架里右边界不断扩展左边界根据条件收缩更新答案的时机各不相同。 “将 x 减到 0 的最小操作数” 这道题相当于“窗口和等于目标值”的最简模型把这个模型吃透后面遇到按字符频率、最大值、中位数做条件的变体时你至少能识别出它们共用同一副骨架。5. 面试实战经验与延伸什么时候该想到滑动窗口5.1 识别滑动窗口题目的几个特征结合这道题总结一下当你看到以下特征时可以优先考虑滑动窗口出现“连续子数组”或“子串”的描述要求满足某个区间条件比如区间和等于 target、区间和小于等于限制、字符频率不超过限制数组元素通常为正整数窗口单调性成立求的是最大长度、最小长度或操作次数。反面情况也要心里有数如果数组元素可能为负数滑动窗口的直接模板就要打问号如果题目要求的是“任意子序列”而不是“连续子数组”那属于动态规划或贪心的范畴滑动窗口不适用。这些判断在面试时能帮你快速缩小方向范围。5.2 一道题的完整思考路径复现我在面试和刷题时总结了一个相对高效的思考顺序很适合在这道题上验证先确认暴力解法能写出来并估算复杂度。比如本题暴力枚举左右取法的组合复杂度是 O(n^2)在 n 较大时不可接受。在题目里找结构线索。这里“从两端取数”正好对应“中间剩余一段连续子数组”是一个很强的线索。尝试把约束反过来看。“移除若干元素”转化为“保留连续部分”往往能让问题简单一个量级。检查目标条件和窗口和是否具备单调性。本题数组元素为正整数不等式关系成立滑动窗口可行。写完主体逻辑后专门花两分钟想边界空数组、总和不够、目标值为 0、找不到窗口。我面试时踩过的一个教训是写代码很快但没把“为什么要把问题反过来看”讲清楚被面试官追问时打磕巴。这道题代码量很小真正的考察点就在于转化的思路和边界的完备性。所以建议你在练习时不要只盯着代码多练习用自己的话把思路讲出来。5.3 滑动窗口思想不只在算法题里滑动窗口并不是刷题才有的概念。信号处理里有滑动窗口滤波把一段时间窗内的数据做统计窗口随着新数据不断前移本质是维护一个局部的统计量TCP 协议里的滑动窗口用来控制发送速率窗口大小决定了网络上同时在途的数据量实时流计算里每来一条新记录就滑动一次窗口做聚合。它们和算法题里的双指针核心逻辑一模一样一个范围在数据流上移动同时维护范围内的某种状态。理解这道题以后你再去接触这些领域会感到一种熟悉感。这也是为什么我建议新手从“将 x 减到 0 的最小操作数”入手学习滑动窗口——它足够简单又足够有代表性。把这里面的思想带走比单纯背下模板有用得多。说实话这道题我第一次做并不顺利甚至在一个简单用例上卡了很久。真正让我觉得“通了”的那一刻不是代码跑通的时候而是想明白“为什么要找中间那段连续子数组”的时候。后来我给朋友讲这道题每次都会先问对方一个问题移除两端的元素剩下的部分有什么特征等对方说出“是连续子数组”这句话后续思路基本就顺了。如果你也正在刷滑动窗口系列我建议把这个题放在最前面它不复杂却能把逆向转化、双指针维护、边界处理这些关键能力都练到。把这道题吃透了再去看滑动窗口最大值、滑动窗口中位数、最小覆盖子串这些变体你会发现自己已经站在一个更稳的起点上。