滑动窗口

Solutions for LeetCode Sliding Window

本文件夹只包含README文档，文档主要整理平时刷题时候遇到的滑动窗口的问题以及对应的题解链接，题解的代码存储在路径其他杂题/中。

滑动窗口指的是这样一类问题的求解方法，在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。

滑动窗口可以处理几乎所有的子串问题

代码框架

private func generateDict(_ list: [Character]) -> [Character: Int] {
    var dict: [Character: Int] = [:]
    for char in list {
        dict[char, default: 0] += 1
    }
    return dict
}

func slidingWindow(_ s: [Character], _ p: [Character]) {
    var window: [Character: Int] = [:]
    var need: [Character: Int] = generateDict(p)
    
    var (left, right, valid) = (0, 0, 0)
    while (right < s.count) {
        // c是将要移入窗口的字符
        let char = s[right]
        // 右移窗口
        right += 1
        // 对窗口内的数据进行更新
        ...
        
        // DEBUG的输出位置
        print("window: [\(left), \(right)]")
        
        // 判断左侧窗口是否需要收缩
        while (window needs shrink) {
            // d 是将要移出窗口的字符
            let d = s[left];
            left += 1
            // 对窗口进行一系列更新
            ...
        }
    }
}