把 x 减到 0最少要操作几次我第一次看到这道题时第一反应是这跟“两数之和”有点像给定一个数组和一个目标值找几个数凑出来。但读完样例我马上意识到不对劲——题目要求每次只能从数组的最左边或最右边取一个元素取出来的数累加后正好等于 x问最少操作几次。这就是 LeetCode 1658中文名“将x减到0的最小操作数”。它的难点不在代码量而在第一步的思维转换如果你用正面模拟“从哪端删”的思路去硬解很快就会被指数级的分支烦死反过来想题目真正想让你找的其实是“数组中间到底能保留多长一段连续子数组”。这篇文章我会按完整的思考链路走一遍先说我一开始怎么踩坑再讲暴力为什么不行然后给出前缀和加哈希表和滑动窗口两种 O(n) 解法最后补充几个我实际提交时才发现的边界坑。无论你是刷题新手还是在准备面试这套“正难则反”的思路都值得记下来。1. 题目到底在问什么从“两端删除”到“中间保留”1.1 先读懂样例背后的操作逻辑题目给一个整数数组 nums 和一个整数 x比如 nums [1,1,4,2,3]x 5。每一次操作你可以在数组的最左边或者最右边移除一个元素同时 x 减去那个元素的值。你要用最少的操作次数让 x 变成 0如果做不到返回 -1。先手动模拟一下样例。如果从右边删第一个删的是 3x 变成 2第二个删的是 2x 变成 0总共 2 次操作。如果从左边删删掉 1 和 1x 还有 3还得再从右边删掉 3总共 3 次操作。所以样例答案是 2。为什么这个题目一开始容易让人懵因为它跟常见的“子数组求和”题长得不一样你删除的元素不是连续的而是被分成两段——一段来自左端一段来自右端中间的部分被完整保留下来。换句话说不管中间过程怎么选择最终被你删除的元素一定可以看成左边取出前 i 个元素右边取出最后 j 个元素中间的 n - i - j 个元素原封不动。而每次操作不会打破两侧的相对顺序所以删除顺序其实不影响最终结果。意识到这一点题目的复杂度就从“过程决策”降到了“结果组合”。1.2 正难则反把删两端的难题转成找连续子数组正面思考为什么难你每次可以选择删左还是删右选完会改变数组的左右边界下一个选择又被影响。这个决策树的分支数量是 2 的指数级即使加记忆化状态也是由左右两个指针构成的二维区间数据规模稍微一大就会卡死。反过来想被删掉的那两段元素的和是 x那中间保留下来的那段连续子数组的和一定等于整个数组的和减去 x。设 total 为整个数组的和target total - x。问题就等价于在数组里找一段连续子数组使它的和等于 target并且让这段子数组尽量长。为什么尽量长因为总操作次数 左边删除个数 右边删除个数 n - 子数组长度。子数组越长操作次数越少。这个反转非常关键。原来我以为是“找最少的删除”实际是“找最长的保留”。很多两端操作的题目都有这个共性后面第 6 节我再展开。2. 为什么暴力解法不是最优从递归回溯到 O(n^2) 枚举2.1 我最初尝试的递归回溯方案第一次做这题时我第一个想法是递归回溯写一个函数 dfs(left, right, rest)每次尝试删左边或右边递归下去找到 rest 变成 0 的最小深度。伪代码大概是def minOperations(nums, x): n len(nums) ans float(inf) def dfs(l, r, rest, steps): nonlocal ans if rest 0: ans min(ans, steps) return if l r or rest 0: return dfs(l 1, r, rest - nums[l], steps 1) dfs(l, r - 1, rest - nums[r], steps 1) dfs(0, n - 1, x, 0) return -1 if ans float(inf) else ans这个代码在数组长度为 15、x 较小时还能跑但一旦 n 上到几万每层两个分支整体是指数级爆炸。它的问题在于完全模拟了“每次选哪端”的过程而没有利用“删除顺序无关”这个性质。哪怕我加一个 (l, r) 的二维记忆化最坏情况也有 O(n^2) 个状态每个状态又可能被多种路径走到实际开销依然很大而且空间消耗也不小。2.2 用前缀和把区间求和压到 O(1)——暴力的本质放弃递归后我转向“枚举删除组合”枚举左边删 i 个右边删 j 个i 和 j 都在 0 到 n 之间判断左边前缀和 右边后缀和是否等于 x。如果等于 x答案就是 i j。为了 O(1) 计算前缀和与后缀和先预处理前缀数组 prepre[k] 表示前 k 个元素的和。右边删 j 个元素的和就是整个数组和减去前 n - j 个元素的和即 total - pre[n - j]。那么条件变成pre[i] (total - pre[n - j]) x整理一下pre[n - j] - pre[i] total - x这个式子很有意思它其实就是“中间一段连续子数组的和为 target”的标准写法。pre[n-j] 是右边删掉 j 个元素后中间部分右边界的前缀和pre[i] 是左边删掉 i 个元素后中间部分左边界的前缀和两者之差就是从 i 到 n-j-1 这段中间区间的和。从这里你应该能感受到枚举 i 和 j 的所有组合是 O(n^2)但因为 n 最大可以到 10^5这个复杂度在严格用例下必然超时。真正的问题变成了如何快速找到一段和为 target 的最长连续子数组。2.3 从暴力推导出的等价式顺着上面的式子继续我们需要找到一个区间 [l, r)使 pre[r] - pre[l] target并且让 r - l 尽量大。这里 l 对应左边删了 l 个r 对应右边删了 n - r 个总共操作 n - (r - l) 次。于是问题被彻底简化在数组里找一个和为 target 的最长连续子数组。怎么找最容易想到的思路有两种一种是前缀和 哈希表另一种是滑动窗口。前者不要求数组元素为正后者要求数组元素为正。本题恰好满足正向元素的条件所以两种都能用。3. 前缀和 哈希表把“找区间”变成“查表”3.1 哈希表里到底存什么要找 pre[r] - pre[l] target 的最大区间可以固定 r在历史前缀和里找一个等于 pre[r] - target 的 pre[l]。为了让区间最长l 要尽可能小也就是那个前缀和出现的位置越早越好。所以哈希表的 key 是“某个前缀和的值”value 是“这个前缀和第一次出现的位置”。初始时把 {0: 0} 放进去表示空前缀的位置是 0。注意这里存的是第一次出现的位置而不是最后一次。这是一个我一开始就记反的点后面第 5 节还会再强调。3.2 边遍历边更新的三个关键细节完整代码def minOperations(nums, x): total sum(nums) target total - x if target 0: return -1 if target 0: return len(nums) n len(nums) first_pos {0: 0} cur 0 max_len -1 for i, num in enumerate(nums): cur num need cur - target if need in first_pos: max_len max(max_len, i 1 - first_pos[need]) if cur not in first_pos: first_pos[cur] i 1 if max_len -1: return -1 return n - max_len三个关键细节第一遍历到索引 i 时cur 是 nums[0..i] 的和当前位置是 i 1。查询 need cur - target 是否存在如果存在说明从 first_pos[need] 到 i 1 这一段的区间和恰好是 target区间长度是 i 1 - first_pos[need]。第二只有当 cur 不在哈希表里时才写入。因为我们需要最早出现位置如果 cur 已经出现过再更新只会让位置变晚导致后续配对的区间更短。所以这个if cur not in first_pos的判断不能省略。第三哈希表要提前放入 {0: 0}否则当某个前缀和刚好等于 target 时例如 nums[0] nums[1] target你会找不到左端点。很多题解漏了这一步测试用例里有一个样例恰好踩中。3.3 复杂度分析与适用条件时间复杂度 O(n)空间复杂度 O(n)。由于只需要一次遍历它比暴力 O(n^2) 优越得多。这个方案最大的优点是它对数组元素是否为负数没有要求。只要前缀和能算哈希表就能工作。即使数组里有负数target 是正的找“和为 target 的最长子数组”也依然可以用这个思路。所以在更一般的场景下前缀和 哈希表是更通用、更稳妥的方案。不过它也有缺点哈希表有额外的空间开销而且思维上稍微绕一点需要你想清楚“存最早位置”而不是“存最新位置”。如果你在比赛或面试中写这个方案注释写清楚 first_pos 的含义能避免很多低级错误。4. 滑动窗口在正数约束下把复杂度压到 O(1) 空间4.1 滑动窗口的单调性从哪来题目有个容易被忽略但关键的限制nums[i] 都是正整数LeetCode 1658 原题的约束是 1 nums[i] 10^4。正数意味着前缀和严格递增也意味着任意一个窗口的区间和在右边界向右移动时一定变大在左边界向右移动时一定变小。这种单调性正是滑动窗口能工作的前提。如果数组里有负数这个前提就不成立右边界右移时窗口和可能变小那你就不能简单地用 while 把左边界挪到合适位置。这也是我经常提醒朋友的一句话滑动窗口不是万能的它依赖于“单调性”。4.2 双指针移动规则与完整代码滑动窗口的标准写法如下def minOperations(nums, x): total sum(nums) target total - x if target 0: return -1 n len(nums) left 0 cur 0 max_len -1 for right, num in enumerate(nums): cur num while cur target: cur - nums[left] left 1 if cur target: max_len max(max_len, right - left 1) if max_len -1: return -1 return n - max_len移动规则可以总结成三句话右指针每次向右扩展一格把 nums[right] 加进窗口这是固定动作。只要窗口和 cur 大于 target就不断把左指针向右移并减去 nums[left]直到 cur 不大于 target。这里必须用 while不是 if。每次收缩完如果 cur 恰好等于 target就记录当前窗口长度并更新最大长度。展开讲讲为什么 while 那么重要。假设当前 cur 100target 10左指针指向的 nums[left] 70。你用 if 只收缩一次cur 变成 30仍然大于 10但你已经跳出收缩逻辑直接去判断if cur target结果不相等白白错过一个可能有效的结果。更糟的是如果你现在继续让右指针向右走cur 只会更大后面所有判断都可能失效。所以这种时刻一定要用 while 把左指针一路挪到 cur target 为止。4.3 和前缀和哈希方案怎么选两个方案放在一起对比方案时间复杂度空间复杂度依赖全正数思路难度前缀和 哈希表O(n)O(n)不依赖较绕滑动窗口O(n)O(1)依赖直观对于本题既然 nums 全为正整数滑动窗口是首选因为代码短、空间小、不容易写错。面试时我一般先说滑动窗口给出最优解然后补一句“如果题目改成可能包含负数滑动窗口就失效了这时可以用前缀和加哈希表兜底”。这样既展示了对原题约束的理解也展示了对更一般场景的掌握。5. 提交前必须卡死的边界条件与测试用例5.1 target 为负数、x 大于数组和的情况target total - x。如果 x total说明你无论如何删删掉的元素之和都到不了 x直接返回 -1。在代码里对应 target 0 的判断。这个判断放最前面可以避免后面进入无意义的循环。有人可能会觉得如果 target 是负数滑动窗口里while cur target在一开始就不成立注意cur 初始为 0如果 target -10 -1 成立所以会把 left 一路挪到数组末尾最终 cur 也变成 0再判断if cur target为 false结果也能得到 -1。看起来好像也能出答案但这样白白多跑了一遍而且逻辑上让人困惑。所以在函数开头显式判断 target 0 并返回 -1既清晰又高效。5.2 需要移除全部元素的特殊样例当 x total 时target 0这意味着中间保留的子数组和为 0。因为所有元素都是正整数唯一可能是空数组也就是要删除所有元素操作次数是 n。这个情况在滑动窗口方案里能被正确处理target0 时每次窗口和 cur 一旦大于 0while 循环就会把左指针一路右移窗口长度最终记录为 0最后返回 n - 0 n。但对于前缀和 哈希表方案如果不在开头显式处理 target 0代码会出问题。因为正数前缀和严格递增cur 不会有重复值need cur - 0 cur永远不会出现在 first_pos 里max_len 会一直是 -1最后错误地返回 -1。所以我会在哈希表方案的函数开头加上if target 0: return len(nums)这个分支看起来简单但第一次写很容易漏。我就是在测试 nums[5], x5 时翻车的这时候正确答案应该是 1而不是 -1。5.3 我实测中踩过的两个坑第一个坑是滑动窗口收缩时用了 if 而不是 while。给一组数据nums [3, 9, 1], x 1total 13target 12。right 移动到索引 1 时cur 12正好等于 target窗口长度 2。继续向右移动到索引 2cur 13需要收缩。如果收缩一次减去 nums[0] 3cur 10left 1仍然不等于 12错过。实际上 nums[0] nums[1] 12最长窗口长度是 2应该返回 n - 2 1。这个坑几乎每个写滑动窗口的人都踩过解法就是 while。第二个坑是哈希表存了“最新位置”而不是“最早位置”。比如当前缀和出现重复时如果你每次无脑更新 first_pos配对出来的区间长度会偏短。正确的做法是只在前缀和第一次出现时写入之后的重复值直接忽略。这个细节隐藏得很深普通测试用例跑不出来但大数据量下会偶发错误。我现在写这类题一定会在注释里写明value 记录最早出现位置。6. 这道题真正想教你的思维模型正难则反6.1 从“最小删除”到“最大保留”的普适思路这道题最值钱的部分不是那十几行代码而是“正难则反”的思维模型。很多题目正面做很难反过来看就通了要在数组两端删掉和为 x 的最少元素等价于保留中间一段最长的、和为 sum - x 的连续子数组。要求“最少操作次数”往往等价于求“最大保留数量”或者“最长满足条件区间”。类似的题还有很多。LeetCode 209 长度最小的子数组LeetCode 713 乘积小于 K 的子数组LeetCode 1248 统计优美子数组它们考察的都是同一种滑动窗口思维。刷题时会发现一旦你意识到“删除”可以转换成“保留”很多看起来复杂的操作题都会瞬间降维。6.2 约束越强解法越巧从同类题看变化还有一个值得留意的点题目限制越强往往有越巧妙的解法。本题的 nums 全是正整数所以可以用 O(1) 空间的滑动窗口如果没有这个限制就得退回前缀和 哈希表。这个“约束驱动解法”的规律在面试中非常实用。如果你把题目的约束改一改比如“可以删除任意位置的元素使和为 x 的最少删除次数”那就从一个双指针题变成了背包/动态规划题。所以当你看到“每次只能从两端”这类描述时第一反应应该是把两端删除想办法等价成中间连续区间而不是真的去模拟删的过程。我自己最初做这题时绕了不少弯路先写了递归再写暴力最后才意识到滑动窗口。如果你也在刷这道题我建议把滑动窗口和前缀和哈希两种方案都手写一遍再用几组极端数据测试比如 x 等于数组总和、x 小于数组中某个单元素、数组只有一个元素等情况。这样踩过一遍坑后面遇到同类题才会真正稳。