当前位置：首页 > news >正文

优选算法系列（2.滑动窗口 _ 上）

news 来源：原创 2025/8/12 20:18:56

解法⼀（暴力求解）（不会超时，可以通过）：一.长度最小的子数组（medium）

题目链接·209. 长度最小的子数组 - 力扣（LeetCode）

解法：

代码：

二：无重复字符的最长⼦串（medium）

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

解法：

代码：

三：最大连续 1 的个数 III（medium）

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

解法：

代码：

四：将 x 减到 0 的最⼩操作数 (medium)

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

解法：

代码：

解法⼀（暴力求解）（不会超时，可以通过）：一.长度最小的子数组（medium）

题目链接·209. 长度最小的子数组 - 力扣（LeetCode）

解法：

解法⼀（暴力 求解）（会超时）：

「从前往后」枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个「起始位置」开始，然后寻找⼀段最短的区间，使得这段区间的和「⼤于等于」目标值。将所有元素作为起始位置所得的结果中，找到「最小值」即可。

在这里我们发现由于数组是一个正整数数组，也就是说这个区间选择的数越多那么数的总和就越大。

如上图所示，当我们选择 2 3 1 2 的区间时候 sum=8 就已经满足题意，此时长度为4，若我们继续向后扩大区间那么长度会一直增大，因此当 right=4 的时候我们其实就可以不继续扩大区间了。

那么此时我们保持 right 不动移动 left ，因为我们知道上一个区间的值 sum=8 当我们移动 left 后只需要减去移出区间的值2我们就可以知道新区间的值

解法二（滑动窗口 ）：

那么这里其实我们就可以使用上述思想来实现利用单调性，使用“同向双指针”来进行优化。

怎么使用呢？看下面的流程就明白了。

代码：

C++：

java:

二：无重复字符的最长⼦串（medium）

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

解法：

解法⼀（暴力求解）（不会超时，可以通过）：

枚举「从每⼀个位置」开始往后，⽆重复字符的子串可以到达什么位置。找出其中长度最⼤的即可。

在往后寻找⽆重复⼦串能到达的位置时，可以利用「哈希表」统计出字符出现的频次，来判断什么时候⼦串出现了重复元素

当出现哈希冲突时right前面的子串就是一个⽆重复字符的子串。

此时我们让 left 向后移动一位如果我们再让 right 重新走那么它又会走到第二个 a 的位置

因为重复的a还在区间内，因此left取前面的字母所出现的⽆重复字符的子串都不会比取 d 时更长

所以我们的正确做法是让left直接跳到冲突的字母之后，保持 right 不变。

这就是滑动窗口的思想。

解法二（滑动窗口）：

研究的对象依旧是⼀段连续的区间，因此继续使⽤「滑动窗⼝」思想来优化。

让滑动窗⼝满⾜：窗⼝内所有元素都是不重复的。

做法：

右端元素 ch 进⼊窗⼝的时候，哈希表统计这个字符的频次：
如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗口，直到 ch 这个元素的频次变为 1 ，然后再更新结果。

如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果

代码：

C++：

java：

三：最大连续 1 的个数 III（medium）

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

解法：

不要去想怎么翻转，不要把问题想的很复杂，这道题的结果⽆非就是⼀段连续的 1 中间塞了 k 个 0 。因此，我们可以把问题转化成：求数组中⼀段最长的连续区间，要求这段区间内 0 的个数不超过 k 个。

解法⼀（暴力求解）：

暴力枚举+0计数器

这里就不讲暴力了。。。

解法二（滑动窗口）：

在暴力求解地思路中，到这种情况时我们应该让 left++ 让 right 重新在left位置开始遍历。

但是如果这样的话我们会发现，right还是会停在之前那个位置，这是因为出窗口的数字为1并不是0，而那k个0都还在窗口里。

因此我们滑动窗口的思路就是 left 和 right 都向后走，left 走的时候要让窗口合法（也就是窗口里的0< k）时left 才停下来。

流程：

初始化⼀些变量 left = 0 , right = 0 , ret = 0 ；
当 right ⼩于数组⼤⼩的时候，⼀直下列循环：

让当前元素进⼊窗⼝，顺便统计到哈希表中；
检查 0 的个数是否超标：

如果超标，依次让左侧元素滑出窗⼝，顺便更新哈希表的值，直到 0 的个数恢复正常；

程序到这⾥，说明窗口内元素是符合要求的，更新结果；
right++ ，处理下⼀个元素；

循环结束后， ret 存的就是最终结果。

代码：

C++：

java：

四：将 x 减到 0 的最⼩操作数 (medium)

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

解法：

题目要求的是数组「左端+右端」两段连续的、和为 x 的最短数组，信息量稍微多⼀些，不易理清思路；我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最长数组。此时，就是熟悉的「滑动窗口」问题了。

转化问题：求 target = sum(nums) - x 。如果 target < 0 ，问题⽆解；
初始化左右指针 l = 0 , r = 0 （滑动窗⼝区间表⽰为 [l, r) ，左右区间是否开闭很重要，必须设定与代码⼀致），记录当前滑动窗⼝内数组和的变量 sum = 0 ，记录当前满足条件数组的最⼤区间⻓度 maxLen = -1 ；
当 r 小于等于数组⻓度时，⼀直循环：