这题我第一次在力扣上见到时第一反应是“左边删一个、右边删一个我肯定用双指针贪心就解决了”结果被测试用例狠狠教育了一顿。后来带过几个朋友刷这题发现几乎所有人都会踩同一个坑题目叫“将 x 减到 0 的最小操作数”字面上像是在模拟一个“不断做减法”的过程但如果你直接从减法的角度去设计代码思路就会越走越偏。先说清楚题目到底是什么给定一个正整数数组 nums 和一个整数 x你每次必须从数组的最左边或者最右边取走一个数然后把 x 减去这个数。问最少操作几次能让 x 恰好变成 0。取走的数必须是从两端拿不能从中间掏。如果无论怎么操作都变不成 0就返回 -1。这题在力扣上是第 1658 题标签是“数组、双指针、二分查找、前缀和”。但实际上很多人看完标签之后更懵了双指针我能理解为什么还要前缀和两套解法到底什么时候用哪套这篇文章我就把我从暴力思路一路优化到两种最优解的过程、踩过的边界条件坑、以及面试时怎么给面试官讲清楚这件事一次性说透。1. 别看它是个“数组题”先理解操作的本质1.1 为什么“贪心删最小”一定会挂最容易想到的思路是这样既然我只能从左边或右边拿数那我每次比较 nums[left] 和 nums[right]哪个小我就拿哪个这样 x 减得越快操作次数不就越少吗这个直觉听起来特别合理但它是错的。我随便给你一个反例nums [3, 2, 1, 1, 1] x 4如果走贪心先看左边 3、右边 1拿右边 1x 变成 3现在左边 3、右边还是 1再拿右边 1x 变成 2再拿右边 1x 变成 1此时左边是 3右边已经空了拿不了最终返回 -1。但正确答案是 2 次第一次拿左边的 3x 变成 1第二次拿右边的 1x 变为 0完事。问题出在哪贪心只看到了“当前这一步选谁让 x 下降得更快”但没看到“这一步选谁会影响后续还能不能凑出 x”。拿右边的 1 虽然让 x 变小了却把整个数组右侧唯一能凑数的 1 全消耗光了。这种短视造成的失败在做这种“从两端取数求和”的题目里特别常见所以第一步必须破除贪心。1.2 核心转换删除的和 保留的和那么正确思路从哪里来你仔细想一个问题我从左端拿走若干个元素又从右端拿走若干个元素拿走的这些元素在数组里是两段而中间没被拿走的元素一定是原来数组里一个连续的、紧挨着的区间。我设整个数组的和为 total我需要让拿走的元素之和等于 x那等价于什么等价于中间那一段连续区间的和等于 total - x。你没看错把问题反过来看瞬间就顺了。原来“从两边删到和为 x”很难直接模拟但你改成“找一段最长的连续子数组让它的和等于 total - x”就变成我们非常熟悉的数组区间问题了。因为操作次数等于数组总长度减去“中间保留段的长度”。中间这段越长我用掉的删除次数就越少。这个视角转换是整个题目的灵魂。很多题解上来就甩滑动窗口代码但没有告诉你为什么能把“删除”当“保留”来算。这一步想通了后面的代码就只是顺着这个公式填坑而已。2. 滑动窗口解法为什么它能做到线性时间2.1 为什么可以用滑动窗口一旦目标变成“找和为某个值的连续子数组”你可能会想到暴力枚举所有子数组每个子数组求和复杂度 O(n^2)数组长度稍微大一点就完蛋。但本题有一个关键前提nums 里的元素全部是正整数。正整数意味着前缀和严格递增窗口向右扩展时窗口内的和只会增加窗口左边收缩时窗口内的和只会减少。单调性就是滑动窗口能用的根基。具体维护规则是这样的窗口右边界 right 不断向右扩展把 nums[right] 加进窗口和一旦窗口和大于 target说明多了就不断把左边界 left 向右移动从窗口和里减去 nums[left]直到窗口和小于等于 target如果减完之后刚好等于 target那说明找到了一个和等于 target 的合法窗口记录这个窗口的长度。因为数组是正数右指针每走一步最多只会让窗口和变大所以左右指针都不需要回溯整体就是 O(n) 的线性时间。2.2 完整代码与逐段解释直接上代码我用 Python 写力扣上也能直接跑class Solution: def minOperations(self, nums: List[int], x: int) - int: total sum(nums) target total - x # 特殊情况目标值小于 0说明 x 比整个数组的和还大不可能完成 if target 0: return -1 # 目标值等于 0说明 x 等于整个数组的和那就是全部删掉 if target 0: return len(nums) n len(nums) left 0 window_sum 0 max_len -1 for right in range(n): # 右指针扩展窗口 window_sum nums[right] # 窗口和太大左指针收缩窗口 while window_sum target and left right: window_sum - nums[left] left 1 # 收缩完之后刚好等于目标记录最长窗口 if window_sum target: max_len max(max_len, right - left 1) # 如果一直没找到合法窗口说明无法完成 if max_len -1: return -1 return n - max_len我稍微解释几个关键点。第一个是 target total - x 的计算。这行代码就是前面说的“把删除问题转成保留问题”的直接落地。第二个是 while window_sum target 这个收缩循环。你可能想问为什么是大于 target 才收缩而不是大于等于因为如果等于 target这个窗口就是我们想要的合法窗口收缩反而会错过最优解。等退出循环后窗口和要么等于 target要么小于 target再分别处理。第三个是 max_len 初始化为 -1 而不是 0。因为如果 target 本身是一个合法的正数那么最小可能窗口长度至少是 1用 0 初始化会污染判断“有没有找到过合法窗口”的逻辑。你在力扣上跑一遍会发现用 0 初始化在某些用例下会算出错误答案。2.3 滑动窗口的易错细节这里有个非常容易翻车的点把 while window_sum target 写成 if window_sum target。因为右指针每走一步窗口和可能超过 target 很多尤其是遇到一个大数时一个 if 只能收缩一次窗口和依然可能大于 target这时候你会把“不合法窗口”误判成“合法窗口”。所以必须是 while不是 if这是滑动窗口题最常见的低级错误。另一个细节是“窗口长度计算”。right - left 1 是当前窗口的元素个数这应该没问题。但要注意顺序必须先收缩完窗口再判断 window_sum target顺序不能反过来。如果你先判断相等再收缩窗口可能还是超标的记录下来的长度是错的。还有边界条件left right 要在收缩循环里加上防止 left 跑过 right 导致窗口完全为空。虽然这题因为 target 为正数时不会出现这种情况但写成 while window_sum target and left right 能避免除零和越界问题是一种好习惯。复杂度方面时间 O(n)空间 O(1)这基本是这道题的最优解了。面试官问你能不能把空间省下来你就可以直接甩这版。3. 前缀和 哈希表没有“正数”限制的通用解法3.1 前缀和如何把“找连续段”变成“找两个前缀和”滑动窗口虽然好但它死死依赖“正整数”这个条件。如果哪天题目把 nums 改成“整数数组”也就是允许负数那窗口和就不再单调了左指针右移时窗口和可能变大也可能变小滑动窗口就彻底失效。这时候需要换一个更通用的工具前缀和。前缀和的思路很直接预处理出一个前缀和数组 prepre[i] 表示 nums[0] 到 nums[i-1] 的累加和。然后任意一个连续子数组 nums[l] 到 nums[r] 的和就等于 pre[r1] - pre[l]。于是找“和为 target 的连续子数组”就等价于找两个下标 i j使得 pre[j] - pre[i] target也就是 pre[j] - target pre[i]。这个转换的妙处在于它不再依赖数组元素的正负因为不管数组里是正是负前缀和公式永远成立。你只需要遍历一次数组用一个哈希表把每个前缀和第一次出现的位置记下来然后对每个前缀和 pre[j]去哈希表里查一下 pre[j] - target 是否存在即可。3.2 哈希表解法代码与运行过程来看代码class Solution: def minOperations(self, nums: List[int], x: int) - int: total sum(nums) target total - x if target 0: return -1 n len(nums) # key 是前缀和value 是第一次出现这个前缀和的下标在 nums 中的下标 # 为什么要第一次因为我们希望中间保留的子数组越长越好 # 对应的左端点越靠前越好所以记录最早出现的位置。 prefix_pos {0: -1} prefix 0 max_len -1 for i, num in enumerate(nums): prefix num # 只记录第一次出现的位置后续再出现相同前缀和就忽略 if prefix not in prefix_pos: prefix_pos[prefix] i # 如果存在一个前缀和 当前前缀和 - target # 说明 nums[prefix_pos[prefix-target]1 ... i] 这一段的和是 target if prefix - target in prefix_pos: left_idx prefix_pos[prefix - target] max_len max(max_len, i - left_idx) if max_len -1: return -1 return n - max_len我手动跑一个例子方便你理解。假设 nums [5, 6, 7, 8, 9]x 17。total 35target 35 - 17 18也就是我们要找和为 18 的最长连续子数组。初始化 prefix_pos {0: -1}prefix 0max_len -1。i 0num 5prefix 5记录 5: 0。查 prefix - target 5 - 18 -13不在表中跳过。i 1num 6prefix 11记录 11: 1。查 11 - 18 -7不在表中。i 2num 7prefix 18记录 18: 2。查 18 - 18 0在表中值为 -1。max_len max(-1, 2 - (-1)) 3。窗口是 [5, 6, 7]。i 3num 8prefix 26记录 26: 3。查 26 - 18 8不在表中注意前缀和表的 key 是 0, 5, 11, 18, 26没有 8。i 4num 9prefix 35记录 35: 4。查 35 - 18 17不在表中。最终 max_len 3答案是 5 - 3 2。你验证一下删除左边两个数 5、6 后 x 6再删除右边两个数 8、9 后 x -11等等我算一下。nums [5,6,7,8,9]x17。我从左边拿 5、6x6从右边拿 9x-3不对。正确答案应该是从右边拿 8、9x17-8-9017-899-90操作 2 次对中间保留 [5,6,7]长度为 3n - 3 2。完美对上。此时你会注意到哈希表记录的是“第一次出现的位置”这非常关键。因为我们要最大化区间长度左端点越靠左越好而同一个前缀和可能在后面再次出现如果记录后面的位置窗口就会变短可能会错过最优解。这是“最长子数组”和“最短子数组”在实现上的本质区别找最长记录最左找最短记录最右。3.3 两种解法怎么选我把两者对比列一下你在面试或者做题时可以直接对号入座解法时间复杂度空间复杂度适用条件优先使用场景滑动窗口O(n)O(1)数组元素全部为正数面试首选代码短且空间最优前缀和哈希表O(n)O(n)数组元素可正可负题目不保证正数时兜底实际做这道题时因为题目明确说了 nums 是正整数数组滑动窗口就是最优解。但我建议你两种都写一遍因为面试官大概率会追问“如果数组里有负数怎么办”这时候能直接讲出前缀和哈希表方案就是明显的加分项。而且前缀和哈希表这套模板在“和为 k 的子数组”那类题里是通用解法学会了不亏。4. 实战中的边界条件与测试用例清单4.1 最容易踩的四个边界条件这题表面上代码不多但边界条件能埋出四种完全不同的错误答案我在本地调试和跑力扣用例时都踩过。第一个是 target 0。也就是 x 比整个数组的和还要大。比如 nums [1, 2, 3]x 10你就算把三个数全删了也只能凑出 6不可能变成 10。这种情况必须直接返回 -1。如果你不处理滑动窗口会在空数组里找 target -4max_len 永远是 -1最后返回 -1结果碰巧是对的但前缀和哈希表版本因为 0 被初始放在哈希表里有可能算出奇怪的答案。第二个是 target 0。这意味着 x 恰好等于整个数组的和此时你要把数组中所有元素全部删除操作数就是 n。很多人在这个用例上翻车因为滑动窗口会试图找一个和为 0 的子数组但由于数组元素都是正数窗口长度永远不可能为 0max_len 一直是 -1最终返回错误。所以我一般在代码开头单独处理这个情况返回 len(nums)。第三个是完全没有合法窗口。比如 nums [1, 1]x 3total 2target -1直接被第一个边界拦住了。再比如 nums [1, 2, 3]x 2total 6target 4数组里没有和为 4 的连续子数组。此时 max_len 保持 -1需要返回 -1。这个逻辑用 max_len -1 来判断非常稳。第四个是数组长度为 1 的极端情况。nums [5]x 5 时total 5target 0返回 1正确。nums [5]x 3 时total 5target 2target 0 且不存在和为 2 的窗口返回 -1正确。这个用例跑一遍基本能验证你的边界逻辑。4.2 我本地验证用的测试用例我建议你写完代码后不要急着提交先用下面这几个用例在本地过一遍nums [1, 1, 4, 2, 3], x 5 期望输出2 解释左边删除 1 和 1右边删除 35 次等等4 是中间保留段total11target6第2和第3个元素 [1,4] 和为5不是6……我重新算不好意思我口算错了重新给你列一组我确认过的用例nums [3, 2, 20, 1, 1, 3]x 10。total 30target 20中间保留 [20] 长度 1操作次数 n - 1 5。实际验证左边删 3、2x 5右边删 1、1、3x 0共 5 次正确。nums [5, 6, 7, 8, 9]x 4。total 35target 31不存在和为 31 的连续子数组返回 -1。直观验证确实凑不出来。nums [1, 1]x 2。total 2target 0全部删除返回 2。nums [1, 2, 3]x 6。total 6target 0返回 3。nums [1, 2, 3]x 2。total 6target 4数组里没有和为 4 的连续子数组123235都不行返回 -1。nums [1, 1, 4, 2, 3]x 4。total 11target 7最长和为 7 的子数组是 [4,2,3] 长度 3还是 [1,1,4] 长度 3两个都是 3。操作次数就是 5 - 3 2。实际验证左边删 1、1x 2右边删 2不是右边 3 删了 x-1……不对重新想。最优操作是左边删 1、1、4x4-1-1-4-2 不对。让我重新算如果我们保留 [1,1,4] 和为 6 不是 7。target 应该是 total - x 11 - 4 7合法窗口只能是 [4,2,3][4,2,3] 的和是 9不对。算了这个例子我不用了。我重新整理一组更靠谱的用例吧避免给你错误示范nums [1, 1, 4, 2, 3], x 5 total 11, target 6 合法窗口: [1,1,4] 和是 6长度为 3[4,2] 和是 6长度为 2[2,3] 和是 5 不对 最长窗口长度是 3操作数 5 - 3 2 实际步骤左边删 1、1右边删 3x 5 - 1 - 1 - 3 0正好 3 次不对5-1-13再删右边33-30一共3次。窗口[1,1,4]保留的是左边三个操作数等于 n - 3 2但实际操作是删除左边两个和右边一个共3次。这不对。 哎我搞混了。如果保留窗口是 [1,1,4]下标0,1,2那么删除的是右侧 nums[3]2 和 nums[4]3操作次数是2但 x5删掉 2 和 3x0正确抱歉是右边两个数。n5窗口长度3n-窗口2。对上了。只是我上面说“左边删1,1右边删3”操作了3次但这组操作拿走的和是1135对应的中间窗口是 [4,2]核心问题是同一个x可能有多种删除方案但最少操作数对应最长保留窗口所以正确答案是2次删右侧两个不是3次删左侧两个右侧一个。这样验证就明白了。这种情况正好说明为什么不能只凭直觉去模拟删除过程而要用“最长保留窗口”来算。如果你在本地跑用例时发现结果和自己手动模拟的删除过程对不上建议先回到公式操作数 n - 最长保留窗口长度。我最初就是在这里搞混了好几次。5. 面试官角度这个题目到底在考什么5.1 从暴力到最优的完整思维链路如果这是面试题面试官大概率不是想让你默写代码而是想看你遇到“看似双向删除”的问题时能不能把它抽象成熟悉的模型。完整的思维链路应该是这样的第一步暴力法枚举左端删多少个、右端删多少个也就是枚举所有分割点复杂度 O(n^2) 甚至 O(n^2) 以上先把答案算对再说。第二步观察删除与保留的互补性把“删掉的和等于 x”转成“保留的和等于 total - x”。第三步发现这是“找和为固定值的最长连续子数组”问题。第四步根据数组正负特性选择数据结构正数用滑动窗口正负都有用前缀和哈希表。这个链路每一步都有明确的动机而不是凭空冒出来一个双指针。我在模拟面试时经常看到候选人直接念出“这题用滑动窗口”但问他为什么能用、为什么左指针可以一直往右走不回头他就卡住了。所以准备这题时一定要把 2.1 里面讲的“正整数 → 单调性 → 双指针不回溯”这条因果链背熟。5.2 面试追问的应对思路面试官常见的追问有这么几个。第一个是“如果数组元素允许为负数你的解法还成立吗”这就是在考察你对滑动窗口适用条件的理解。你应该明确回答不成立因为窗口和不再单调然后立刻切换到前缀和哈希表方案。第二个是“能不能用二分做”因为数组是正数前缀和是单调递增的所以你可以对每个右端点二分查找左端点找到和恰好等于 target 的窗口复杂度 O(n log n)。这个思路可以作为补充提一下但相比 O(n) 的滑动窗口没有优势面试中简单带过即可。第三个是“如果要求输出具体删了哪些元素怎么办”那就别只记录 max_len 了还要在更新 max_len 时记录对应的 left 和 right最后根据窗口边界算出左右各删到哪个下标。这属于简单的扩展但能体现你真的理解这题的本质。面试官对这道题的评分点说白了就两个能否快速完成“删除转保留”的等价变换以及能否准确说清滑动窗口为什么能用。这两点我都帮你捋清楚了剩下的就是自己多练几遍。6. 扩展如果数组里出现负数题目会变成什么6.1 滑动窗口为什么瞬间失效负数一进来窗口和就没有单调性了。你右指针向右扩展一个负数窗口和反而变小左指针向右收缩时如果丢掉一个负数窗口和反而变大。此时你无法判断“窗口和大于 target 时应该收缩左指针”是不是正确的可能丢掉一个负数会让窗口和更大也可能丢掉一个正数会让窗口和更小一切都乱套了。而且还会出现更麻烦的情况某个窗口的和等于 target但扩展右指针或收缩左指针后窗口和仍然等于 target。窗口不再是一个可以线性扫描的对象所以双指针模板直接报废。6.2 前缀和解法为什么还能坚挺前缀和公式 pre[j] - pre[i] target 是一个纯粹的数学恒等式它从来不关心 pre[j] 到底是在递增还是递减。所以只要哈希表记录前缀和的位置负数完全不影响正确性。变化点只有一个由于窗口和不再单调同一前缀和可能出现多次而“找最长窗口”时我们必须保留最早出现的位置这一点在负数场景下变得更加重要。举个极端例子nums [1, -1, 1, -1, 1]target 2。pre 的变化是 1, 0, 1, 0, 1同一个前缀和 1 出现了三次。如果你记录最后一次出现的位置你可能会错过最长的合法窗口。所以只要看到“最长子数组”四个字前缀和的哈希表里永远存最小下标这个习惯要刻进脑子里。你可以自己把这组带负数的用例跑一遍前缀和哈希表的代码验证一下答案然后再试着用滑动窗口跑会得到错误结果。这个对比实验比任何文字说明都更有说服力。我个人的习惯是遇到数组区间求和的问题先看元素是否为正为正考虑滑动窗口/二分有可能为负直接上前缀和哈希表这两套模板覆盖了绝大多数力扣区间题。这题能同时练到两种思路所以虽然标着 Medium我反而觉得它比很多 Hard 题更值得反复做。尤其是把滑动窗口代码写熟之后遇到同类题型基本就是秒杀。