滑动窗口思想
模板
/* 滑动窗口算法框架 */
func slidingWindow(_ s: String, _ t: String) {
let sArray = [Character](s)
var win = Dictionary<Character, Int>() // 保存滑动窗口字符集
var need = Dictionary<Character, Int>() // 保存需要的字符集
for c in t {
need[c, default: 0] += 1
}
var left = 0 ,right = 0 // 窗口
var valid = 0 // 匹配次数
while right < sArray.count {
// rightItem 是将移入窗口的字符
let rightItem = sArray[right]
// 右移窗口
right += 1
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
print("window: [\(left), \(right))\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
let leftItem = sArray[left]
// 左移窗口
left += 1
// 进行窗口内数据的一系列更新
...
}
}
}
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}需要变化的地方
1、右指针右移之后窗口数据更新
2、判断窗口是否要收缩
3、左指针右移之后窗口数据更新
4、根据题意计算结果
示例
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串
//https://leetcode-cn.com/problems/minimum-window-substring/solution/swift-hua-dong-chuang-kou-you-hua-by-hu-cheng-he-d/
//执行用时：168 ms, 在所有 Swift 提交中击败了70.27%的用户
//内存消耗：15.5 MB, 在所有 Swift 提交中击败了96.67%的用户
func minWindow(_ s: String, _ t: String) -> String {
let sArray = [Character](s)
var win = Dictionary<Character, Int>() // 保存滑动窗口字符集
var need = Dictionary<Character, Int>() // 保存需要的字符集
for c in t {
need[c, default: 0] += 1
}
var left = 0 ,right = 0 // 窗口
var match = 0 // match匹配次数
var start = 0 , end = 0
var minLength = Int.max
while right < sArray.count {
let rightItem = sArray[right]
right += 1
// 在需要的字符集里面，添加到窗口字符集里面
if need[rightItem] != nil{
win[rightItem, default: 0] += 1
// 如果当前字符的数量匹配需要的字符的数量，则match值+1
if win[rightItem] == need[rightItem]{
match += 1
}
}else{
continue
}
// 当所有字符数量都匹配之后，开始缩紧窗口
while match == need.count {
if right - left < minLength {
start = left
end = right
minLength = end - start
}
let leftItem = sArray[left]
left += 1
// 左指针指向不在需要字符集则直接跳过
if need[leftItem] != nil{
// 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一
// 因为win里面的字符数可能比较多，如有10个A，但需要的字符数量可能为3
// 所以在压死骆驼的最后一根稻草时，match才减一，这时候才跳出循环
if win[leftItem] == need[leftItem]{
match -= 1
}
win[leftItem]! -= 1
}
}
}
return minLength == Int.max ? "" : String(sArray[start..<end])
}
//print(minWindow("ADOBECODEBANC","ABC"))给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
//https://leetcode-cn.com/problems/permutation-in-string/solution/swift-hua-dong-chuang-kou-by-hu-cheng-he-da-bai-sh/
//执行用时：456 ms, 在所有 Swift 提交中击败了47.06%的用户
//内存消耗：13.9 MB, 在所有 Swift 提交中击败了100.00%的用户
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
let s2Array = [Character](s2)
var win = Dictionary<Character, Int>() // 保存滑动窗口字符集
var need = Dictionary<Character, Int>() // 保存需要的字符集
for c in s1 {
need[c, default: 0] += 1
}
var left = 0 ,right = 0 // 窗口
var match = 0 // match匹配次数
while right < s2Array.count {
let rightItem = s2Array[right]
right += 1
// 在需要的字符集里面，添加到窗口字符集里面
if need[rightItem] != nil{
win[rightItem, default: 0] += 1
// 如果当前字符的数量匹配需要的字符的数量，则match值+1
if win[rightItem] == need[rightItem]{
match += 1
}
}else{
continue
}
// 当所有字符数量都匹配之后，开始缩紧窗口
while match == need.count {
if right - left == s1.count {
return true
}
let leftItem = s2Array[left]
left += 1
// 左指针指向不在需要字符集则直接跳过
if need[leftItem] != nil{
// 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一
// 因为win里面的字符数可能比较多，如有10个A，但需要的字符数量可能为3
// 所以在压死骆驼的最后一根稻草时，match才减一，这时候才跳出循环
if win[leftItem] == need[leftItem]{
match -= 1
}
win[leftItem]! -= 1
}
}
}
return false
}给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
//https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/swift-hua-dong-chuang-kou-by-hu-cheng-he-da-bai--2/
//执行用时：2008 ms, 在所有 Swift 提交中击败了16.67%的用户
//内存消耗：14.7 MB, 在所有 Swift 提交中击败了100.00%的用户
func findAnagrams(_ s: String, _ p: String) -> [Int] {
let sArray = [Character](s)
var win = [Character: Int]() // 保存滑动窗口字符集
var need = [Character: Int]() // 保存需要的字符集
for c in p {
need[c, default: 0] += 1
}
var left = 0 ,right = 0 // 窗口
var match = 0 // match匹配次数
var startIndexs = [Int]()
while right < sArray.count {
let rightItem = sArray[right]
right += 1
// 在需要的字符集里面，添加到窗口字符集里面
if let needItem = need[rightItem] {
win[rightItem, default: 0] += 1
// 如果当前字符的数量匹配需要的字符的数量，则match值+1
if win[rightItem] == needItem{
match += 1
}
}else{
continue
}
while match == need.count {
if right - left == p.count {
startIndexs.append(left)
}
let leftItem = sArray[left]
left += 1
if let needItem = need[leftItem] {
if win[leftItem] == needItem{
match -= 1
}
win[leftItem]! -= 1
}
}
}
return startIndexs
}longest-substring-without-repeating-characters
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/swift-hua-dong-chuang-kou-by-hu-cheng-he-da-bai--2/
//执行用时：76 ms, 在所有 Swift 提交中击败了59.25%的用户
//内存消耗：14.4 MB, 在所有 Swift 提交中击败了89.78%的用户
func lengthOfLongestSubstring(_ s: String) -> Int {
let sArray = [Character](s)
var win = Dictionary<Character, Int>()
var left = 0 ,right = 0 // 窗口
var maxLength = 0
while right < sArray.count {
let rightItem = sArray[right]
right += 1
win[rightItem, default: 0] += 1
while win[rightItem]! > 1 {
let leftItem = sArray[left]
left += 1
win[leftItem]! -= 1
}
maxLength = max(maxLength,right - left)
}
return maxLength
}总结
和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
核心步骤
right 右移
收缩
left 右移
求结果
练习
最后更新于