定长滑动窗口题解思路
发表于|更新于|算法学习
原文发表于 2026-07-30,更新于 2026-07-30;原文未提供具体时刻。
定长滑动窗口的解题思路是很明了的。
首先,滑动窗口的窗口大小是固定的,这就意味着我们没有必要在窗口大小上面费心思,只需要考虑好滑动窗口的变化规则就行了。
其次,在做题的时候,要先考虑到“入”“判断”“出”这几种情况,只要把这几种情况解决了,就好做了。
最后,在这种定长滑动窗口的循环中,我们通常使用 for 循环,因为可以用 i-k+1 找到窗口最左边的数组位置。
当右端点为 i、窗口长度为 k 时,窗口范围就是:
1 | [i-k+1, i] |
当 i-k+1 < 0 时,窗口还没有凑够 k 个元素,暂时不更新答案。
整理说明:原页面的“浏览量:2”是旧网站统计数据,不作为正文或新站浏览量迁移。
文章作者: Decwoveh
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Decwoveh的学习周记!
相关推荐
2026-09-25
可获得的最大点数:逆向思维与定长滑动窗口
本文由旧博客内容整理迁入。原发布日期未提供,页面日期为本次整理日期。 题目几张卡牌排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动,你可以从行的开头或者末尾拿一张卡牌,最终必须正好拿 k 张卡牌。你的点数就是拿到手中的所有卡牌的点数之和。 给你整数数组 cardPoints 和整数 k,返回可以获得的最大点数。 示例示例 1 12输入:cardPoints = [1,2,3,4,5,6,1], k = 3输出:12 解释:第一次行动,不管拿哪张牌,点数都是 1。最优策略是拿右边的三张牌,最终点数为 1 + 6 + 5 = 12。 示例 2 12输入:cardPoints = [2,2,2], k = 2输出:4 解释:无论拿起哪两张卡牌,可获得的点数总是 4。 示例 3 12输入:cardPoints = [9,7,7,9,7,7,9], k = 7输出:55 解释:必须拿起所有卡牌,可以获得的点数为所有卡牌的点数之和。 示例 4 12输入:cardPoints = [1,1000,1], k = 1输出:1 解释:无法拿到中间那张...
2026-09-25
尽可能使字符串相等:预算限制下的滑动窗口
本文由旧博客内容整理迁入。原发布日期未提供,页面日期为本次整理日期。 题目给你两个长度相同的字符串 s 和 t。 将 s 中的第 i 个字符变到 t 中的第 i 个字符,需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值之差的绝对值。 用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。 如果可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。如果不存在这样的子字符串,则返回 0。 解题思路这道题主要注意一个地方:字符变换所选的位置必须连续,因此也可以归入滑动窗口这一类。 先计算每个位置的转换开销,再维护区间的开销和。 C++ 题解(保留原实现)12345678910111213141516171819202122232425262728class Solution {public: int equalSubstring(string s, string t, int maxCost) { ...
2026-09-25
水果成篮:最多两种元素的滑动窗口
本文由旧博客内容整理迁入。原发布日期未提供,页面日期为本次整理日期。 题目你正在探访一家农场,农场从左到右种植了一排果树。这些树用整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果种类。 你想尽可能多地收集水果,但需要遵守以下规则: 只有两个篮子,每个篮子只能装单一类型的水果,数量不限。 可以选择任意一棵树开始采摘,必须从每棵树(包括开始采摘的树)上恰好摘一个水果。 每采摘一次,向右移动到下一棵树。 一旦水果不符合篮子的水果类型,就必须停止采摘。 给你整数数组 fruits,返回可以收集的水果的最大数目。 示例示例 1 12输入:fruits = [1,2,1]输出:3 解释:可以采摘全部 3 棵树。 示例 2 12输入:fruits = [0,1,2,2]输出:3 解释:可以采摘 [1,2,2]。如果从第一棵树开始,只能采摘 [0,1]。 示例 3 12输入:fruits = [1,2,3,2,2]输出:4 解释:可以采摘 [2,3,2,2]。如果从第一棵树开始,只能采摘 [1,2]。 示例 4 12输入:fruits = [3,3,3,1,...
2026-09-25
每个元素最多出现 K 次的最长子数组
本文由旧博客内容整理迁入。原发布日期未提供,页面日期为本次整理日期。 题目给你一个整数数组 nums 和一个整数 k。 一个元素 x 在数组中的频率,指的是它在数组中的出现次数。如果一个数组中所有元素的频率都小于等于 k,那么称这个数组为好数组。 请返回 nums 中最长好子数组的长度。子数组是数组中一段连续非空的元素序列。 示例示例 1 12输入:nums = [1,2,3,1,2,3,1,2], k = 2输出:6 解释:最长好子数组是 [1,2,3,1,2,3],值 1、2、3 的频率均未超过 2。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是长度为 6 的好子数组。 示例 2 12输入:nums = [1,2,1,2,1,2,1,2], k = 1输出:2 解释:最长好子数组是 [1,2] 或 [2,1],其中每个元素只出现一次。 示例 3 12输入:nums = [5,5,5,5,5,5,5], k = 4输出:4 解释:最长好子数组是 [5,5,5,5],值 5 的频率没有超过 4。 解题思路直接见题解:统计窗口内元素的出现次数,只要新加入的元素...
2026-09-25
删掉一个元素以后全为 1 的最长子数组
本文由旧博客内容整理迁入。原发布日期未提供,页面日期为本次整理日期。 题目给你一个二进制数组 nums,你需要从中删掉一个元素。 请你在删掉元素的结果数组中,返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组,请返回 0。 示例示例 1 12输入:nums = [1,1,0,1]输出:3 解释:删掉位置 2 的数后,[1,1,1] 包含 3 个 1。 示例 2 12输入:nums = [0,1,1,1,0,1,1,0,1]输出:5 解释:删掉位置 4 的数字后,数组为 [0,1,1,1,1,1,0,1],最长全 1 子数组为 [1,1,1,1,1]。 示例 3 12输入:nums = [1,1,1]输出:2 解释:必须删除一个元素。 解题思路这道题很有意思,处理方式也非常巧妙,但是依旧可以沿用不定长滑动窗口的做法。 维护一个最多包含一个 0 的窗口。因为必须删除一个元素,所以候选答案是窗口长度减一,即 right-left。即使整个窗口都是 1,也必须减一。 C++ 题解123456789101112131415161718class Solution ...
2026-09-25
无重复字符的最长子串:用 while 收缩窗口
本文由旧博客内容整理迁入。原发布日期未提供,页面日期为本次整理日期。 题目给定一个字符串 s,请找出其中不含有重复字符的最长子串的长度。 示例示例 1 12输入:s = "abcabcbb"输出:3 解释:无重复字符的最长子串是 "abc",长度为 3。"bca" 和 "cab" 也是正确答案。 示例 2 12输入:s = "bbbbb"输出:1 解释:无重复字符的最长子串是 "b",长度为 1。 示例 3 12输入:s = "pwwkew"输出:3 解释:无重复字符的最长子串是 "wke",长度为 3。答案必须是子串的长度,"pwke" 是子序列,不是子串。 提示 0 <= s.length <= 5 * 10^4 s 由英文字母、数字、符号和空格组成。 解题思路这道题是一个很经典的题目。虽然是不定长滑动窗口,但是依旧可以借鉴滑动窗口的思路:“入、更新、出”。 我一开始没想出来,原因...
评论
公告
本网站仅学习使用,各个功能还在实现中,無钱买好的数据库,故切勿登录以及在评论下面追加评论(登录是给有钱了之后搞得接口,别点!)评论加邮箱可显示QQ头像,否则全默认
