[算法]滑动窗口技巧在算法题中的应用总结
前言
概序
对于滑动窗口这个概念，可能之前有学习TCP/IP协议的朋友有比较熟悉的印象，TCP滑动窗口分为接受窗口，发送窗口滑动窗口协议是传输层进行流控的一种措施，接收方通过通告发送方自己的窗口大小，从而控制发送方的发送速度，从而达到防止发送方发送速度过快而导致自己被淹没的目的。而本次探讨的是在解题的一种思路。最初我学习到类似滑动窗口的概念是在《数据结构与算法分析 Java语言描述》遇到一个求最大子序列和问题，后来又在LeetCode遇到不重复字串的问题。两者解法有点类似。总结下来，参考前人的经验，了解了一种特别的处理方法叫滑动窗口。滑动窗口解题过程是指，通过选定左下标$P_$与右下标$P_$截取有序集合$A$的子集，进而通过判定该子集是否符合问题的解。在本篇博客中我想收集几个能够用于滑动窗口的例子。
包含的算法题目
-
《数据结构与算法分析 Java语言描述》-最大子序列和问题：
给定(可能有负)的整数$A_{1}，A_{2}，··· ，A_{N}$，求$\sum_{k=i}^jA_{k}$的最大值。
输入: -2，11，-4，13，-5，-2
输出: 20
解释: 从$A_{2}$到$A_{4}$，元素连续字子集中只有这个子集的和最大 -
LeetCode-3. 无重复字符的最长子串:
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 -
LeetCode-76. 最小覆盖子串:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
示例:
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" -
LeetCode-209. 长度最小的子数组:
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。 -
LeetCode-438.找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。
输入: s: "cbaebabacd" p: "abc"
输出:[0, 6]
解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词，起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。 -
LeetCode-567. 字符串的排列:
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
输入: s1 = "ab" s2 = "eidbaooo"
输出: true
解释: s2 包含 s1 的排列之一 ("ba"). -
其它
解析
参考
-
马克·艾伦·维斯(Mark Allen Weiss) 著,冯舜玺 陈越 译 ,《数据结构与算法分析 Java语言描述》,第2.2节 要分析的问题, 第22页至第23页
-
IEEE Localization with Sliding Window Factor Graphs on Third-Party Maps for Automated Driving