type
status
slug
summary
tags
category
password
date
icon
算法题手撕
滑动窗口（定长/不定长/多指针）
定长滑动窗口
我总结成三步：入-更新-出。
入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。
以上三步适用于所有定长滑窗题目。
作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/1/tao-lu-jiao-ni-jie-jue-ding-chang-hua-ch-fzfo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
首先计算初始窗口[0,k]中元音字母的个数，然后这个窗口开始向右滑动一，此时分为三种情况：
- 右侧新进入窗口的字母为元音字母，左侧移出窗口的字母也是元音字母，这样一进一出抵消掉了
- 右侧新进入窗口的字母为元音字母，左侧移出窗口的字母非元音字母，此时元音字母个数+1
- 右侧新进入窗口的字母非元音字母，左侧移出窗口的字母为元音字母，此时元音字母个数-1
643. 子数组最大平均数 I
1343. 大小为 K 且平均值大于等于阈值的子数组数目 1317
2090. 半径为 k 的子数组平均值 1358
2379. 得到 K 个黑块的最少涂色次数 1360
1052. 爱生气的书店老板 1418
2841. 几乎唯一子数组的最大和 1546
2461. 长度为 K 子数组中的最大和 1553
1423. 可获得的最大点数 1574
2134. 最少交换次数来组合所有的 1 II 1748
2653. 滑动子数组的美丽值 1786
567. 字符串的排列
438. 找到字符串中所有字母异位词
2156. 查找给定哈希值的子串 2063
2953. 统计完全子字符串 2449
346. 数据流中的移动平均值（会员题）
1100. 长度为 K 的无重复字符子串（会员题）
1852. 每个子数组的数字种类数（会员题）
2067. 等计数子串的数量（会员题）
2107. 分享 K 个糖果后独特口味的数量（会员题）
不定长滑动窗口（求最长/最大）
滑动窗口，重复字符只有可能来自于右边的字符
1493. 删掉一个元素以后全为 1 的最长子数组 1423
2730. 找到最长的半重复子字符串 1502
904. 水果成篮 1516
1695. 删除子数组的最大得分 1529
2958. 最多 K 个重复元素的最长子数组 1535
2024. 考试的最大困扰度 1643
1004. 最大连续1的个数 III 1656
1438. 绝对差不超过限制的最长连续子数组 1672
2401. 最长优雅子数组 1750
1658. 将 x 减到 0 的最小操作数 1817
1838. 最高频元素的频数 1876
2516. 每种字符至少取 K 个 1948
2831. 找出最长等值子数组 1976
2106. 摘水果 2062
1610. 可见点的最大数目 2147
2781. 最长合法子字符串的长度 2204
2968. 执行操作使频率分数最大 2444
395. 至少有 K 个重复字符的最长子串
1763. 最长的美好子字符串
159. 至多包含两个不同字符的最长子串（会员题）
340. 至多包含 K 个不同字符的最长子串（会员题）
不定长滑动窗口（求最短/最小）
需要一个长度来存储答案节点，然后懂得舍去前面的，才能遇到后面更好的
1234. 替换子串得到平衡字符串 1878
1574. 删除最短的子数组使剩余数组有序 1932
76. 最小覆盖子串
面试题 17.18. 最短超串
不定长滑动窗口（求子数组个数）
2799. 统计完全子数组的数目 1398
1358. 包含所有三种字符的子字符串数目 1646
2962. 统计最大元素出现至少 K 次的子数组 1701
2302. 统计得分小于 K 的子数组数目 1808
2537. 统计好子数组的数目 1892
2762. 不间断子数组 1940
2972. 统计移除递增子数组的数目 II 2153
2743. 计算没有重复字符的子字符串数量（会员题）
多指针滑动窗口
930. 和相同的二元子数组 1592
1248. 统计「优美子数组」 1624
2563. 统计公平数对的数目 1721
1712. 将数组分成三个子数组的方案数 2079
2444. 统计定界子数组的数目 2093
992. K 个不同整数的子数组 2210
1989. 捉迷藏中可捕获的最大人数（会员题）
- 作者:fufu酱
- 链接:https://csfufu.life/article/3ab1da58-9d20-4054-acbd-65140c520df7
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章