题目描述
思路解析动画文字版
记住「拿两端和为 x = 留中间和为 target=8;拿最少 = 留最长」,下面每一格都在套它。
这一排是数组,全是正整数。我们要找和正好等于 target=8 的最长连续段。窗口从空开始,右指针一格格扩,盯住窗口和 cur 和当前最长。
右指针到第 0 位(值 1),加进窗口,窗口和变成 1。还没到 target=8,接着右扩。
右指针到第 1 位(值 2),加进窗口,窗口和变成 3。还没到 target=8,接着右扩。
右指针到第 2 位(值 3),加进窗口,窗口和变成 6。还没到 target=8,接着右扩。
右指针到第 3 位(值 1),加进窗口,窗口和变成 7。还没到 target=8,接着右扩。
右指针到第 4 位(值 1),加进窗口,窗口和变成 8。正好等于 target=8!这是一个候选中间段。
这段绿色窗口 [0, 4] 的和正好是 8、长度 5。比之前的最长还长,最长中间段刷新成 5,对应操作数 8−5=3。
右指针到第 5 位(值 1),加进窗口,窗口和变成 9。它比 target=8 大了(红),下一步要左缩。
窗口和超了,左指针右移一格、把第 0 位的 1 移出,和降到 8。正好回到 target!
这段绿色窗口 [1, 5] 的和正好是 8、长度 5。没超过已记的最长 5,操作数保持 3。
右指针到第 6 位(值 2),加进窗口,窗口和变成 10。它比 target=8 大了(红),下一步要左缩。
窗口和超了,左指针右移一格、把第 1 位的 2 移出,和降到 8。正好回到 target!
这段绿色窗口 [2, 6] 的和正好是 8、长度 5。没超过已记的最长 5,操作数保持 3。
右指针到第 7 位(值 3),加进窗口,窗口和变成 11。它比 target=8 大了(红),下一步要左缩。
窗口和超了,左指针右移一格、把第 2 位的 3 移出,和降到 8。正好回到 target!
这段绿色窗口 [3, 7] 的和正好是 8、长度 5。没超过已记的最长 5,操作数保持 3。
扫完全程,和等于 target=8 的最长中间段是绿色这段 [0, 4]、长 5。留下它最长,拿走的就最少:答案 = 8 − 5 = 3 次。没有去枚举两端怎么拿,一遍滑窗就解决。
边界先想清:x=总和返回 n、x>总和返回 -1、找不到中间段返回 -1。
面试常考:为什么转成留中间最长,以及答案为何是 n−最长。
参考代码
from typing import Listclass Solution: def minOperations(self, nums: List[int], x: int) -> int: target = sum(nums) - x if target < 0: return -1 if target == 0: return len(nums) left = cur = best = 0 best = -1 for right, v in enumerate(nums): cur += v while cur > target: cur -= nums[left] left += 1 if cur == target: best = max(best, right - left + 1) return -1 if best == -1 else len(nums) - best复杂度
- 时间：O(n)，左右指针各只前进一遍,每个元素进出窗口各一次
- 空间：O(1)，只用 left/cur/best 几个变量
易错点
面试追问把动画讲成自己的话
追问为什么不直接对「两端怎么拿」做搜索?
追问为什么答案是 n − 最长段,而不是最长段本身?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除子数组的最大得分
LeetCode 1695 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题