算法练习：滑动窗口(Sliding Window)

[ShannonChenCHN]

题目列表

• 3. 无重复字符的最长子串（难度中等）（注：本题同剑指 Offer 48. 最长不含重复字符的子字符串）⭐️
• 209. 长度最小的子数组（难度中等）⭐️
• 76. 最小覆盖子串（难度困难）⭐️
• 239. 滑动窗口最大值 （难度困难）（注：本题同 剑指 Offer 59 - I. 滑动窗口的最大值）⭐️
• 剑指 Offer 59 - II. 队列的最大值（难度中等）
• 567. 字符串的排列（难度中等）
• 30. 串联所有单词的子串（难度困难）
• 438. 找到字符串中所有字母异位词

总结

• 什么是滑动窗口算法
• 需要记住滑动窗口算法的基本步骤
• 滑动窗口算法适合用来解决哪一类问题？

[ShannonChenCHN]

理论知识

1. 什么是滑动窗口

滑动窗口是指用两个指针围成一个区间来扫描一个数组或者字符串，我们可以把这个区间叫做”可滑动的窗口“。

比如，我们有这样一个数组：

[a b c d e f g h]

那么一个大小为 3 的 window 就会有这样的扫描过程：

[a b c d e f g h]
 ↑   ↑
[a b c d e f g h]
   ↑   ↑
[a b c d e f g h]
     ↑   ↑
[a b c d e f g h]
       ↑   ↑
[a b c d e f g h]
         ↑   ↑
[a b c d e f g h]
           ↑   ↑

滑动窗口算法的基本步骤是：

1. Use two pointers: start and end to represent a window.
2. Move end to find a valid window.
3. When a valid window is found, move start to find a smaller window.

滑动窗口这类问题的解法模板见：https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems/25861

2. 合适用滑动窗口来解决的典型问题有哪些？

The Sliding window is a problem-solving technique for problems that involve arrays/lists. These problems are easy to solve using a brute force approach in O(n^2) or O(n^3). Using the 'sliding window' technique, we can reduce the time complexity to O(n).

Great article on this is here: https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66

So the first thing you want to be able to do is to identify a problem that uses a sliding window paradigm. Luckily, there are some common giveaways:

• The problem will involve a data structure that is ordered and iterable like an array or a string
• You are looking for some subrange in that array/string, like the longest, shortest or target value.
• There is an apparent naive or brute force solution that runs in O(N²), O(2^N) or some other large time complexity.

But the biggest giveaway is that the thing you are looking for is often some kind of optimal, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

简而言之，滑动窗口一般用来解决这类问题：从一个数组/字符串中找出一个符合条件的最长或最短子数组/子串。

参考

• 滑动窗口算法基本原理与实践
• What is Sliding Window Algorithm? Examples? - Stack Overflow
• How to Solve Sliding Window Problems | by Sergey Piterman ...
• An Introduction to Sliding Window Algorithms | by Jordan Moore

[ShannonChenCHN]

3. 无重复字符的最长子串（难度中等）

注：本题同剑指 Offer 48. 最长不含重复字符的子字符串

2021.03.20 05:40 pm ~ 06:30pm, 07:30 pm ~ 09:00pm

解法一：暴力法

解法二：滑动窗口

大概思路：两个指针 start 和 end，start 指针暂时不动，滑动 end 指针，记录长度，如果遇到重复的字符，就将 start 指针移到重复字符上一次出现过的位置后面。另外，我们需要一个哈希表用来记录某个出现过的字符在字符串中的位置。

具体思路可以对照这个题解中的图，看中文版官方题解的代码，不过官方题解需要优化一下，最终版的代码见英文站最高票题解。

注意点：

• 遇到重复的字符移动 start 指针时，需要检测哈希表中记录的该字符上一次出现过的位置是否在窗口内

这道题看思路并不难，但是实现起来却很容易出错，建议多做几次。

时间复杂度：O(N)，其中 N 是字符串的长度。因为总共只遍历整个字符串一次。
空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        guard s.count > 0 else {
            return 0
        }
        var maxLength = 0
        var start = 0, end = 0
        var records: [Character : Int] = [:]
        for c in s {
            if let indexInRecords = records[c], indexInRecords >= start {
                // 这里为什么还要跟 start 比较？保证是在窗口内重复的
                // 考虑 "abba" 这种场景，当 records["a"] == 0，start == 2，end == 3 时
                start = indexInRecords + 1  // 左边界直接移到重复字母的后面
            }
            maxLength = max(maxLength, end - start + 1) // 更新结果
            records[c] = end  // 更新记录
            end += 1    // 右边界后移一位
        }
        
        return maxLength
    }
}

[ShannonChenCHN]

209. 长度最小的子数组（难度中等）

2021.03.21 10:00 am ~ 11:20 am

解法：滑动窗口

大概思路：两个指针 start 和 end，start 指针暂时不动，滑动 end 指针，记录当前区间的sum，如果遇发现 sum > target，就将 start 指针后移一位，并将 sum 减掉移出窗口的数。

注意点：

• 当 sum > target 时，将 start 指针后移一位之后，还要继续判断是否满足 sum <= target

具体思路可以对照官方题解中的动画。

具体 case 分析：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

[0, 0] sum = 2  小于目标值，右指针继续往后走
[0, 1] sum = 5  小于目标值，右指针继续往后走
[0, 2] sum = 6  小于目标值，右指针继续往后走
[0, 3] sum = 8  超过目标值了，把数据记录下来(`minLength = 4`)，右指针不能再往后走了，左指针后移一步
[1, 3] sum = 6  小于目标值，右指针继续往后走
[1, 4] sum = 10 超过目标值了，把数据记录下来(`minLength = 4`)，右指针不能再往后走了，左指针后移一步
[2, 4] sum = 7  达到目标值了，把数据记录下来(`minLength = 3`)，右指针不能再往后走了，左指针后移一步
[3, 4] sum = 6  小于目标值，右指针继续往后走
[3, 5] sum = 9  超过目标值了，把数据记录下来(`minLength = 3`)，右指针不能再往后走了，左指针后移一步
[4, 5] sum = 7  已经达到目标值了，把数据记录下来(`minLength = 2`)，右指针不能再往后走了，左指针后移一步 
[5, 5] sum = 3  小于目标值，右指针继续往后走
[5, 6]          右指针越界，停止遍历 

输入：target = 4, nums = [1,4,4]
输出：1

[0, 0] sum = 1 小于目标值，右指针继续往后走
[0, 1] sum = 5 超过目标值了，把数据记录下来(`minLength = 1`)，右指针不能再往后走了，左指针后移一步
[1, 1] sum = 4 达到目标值了，把数据记录下来(`minLength = 1`)，因为左指针和右指针重叠了，所以左右指针都后移一步
[2, 2] sum = 4 达到目标值了，把数据记录下来(`minLength = 1`)，因为左指针和右指针重叠了，所以左右指针都后移一步
[3, 3]         左右指针越界，停止遍历 

初版：

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        var minLength = Int.max
        var left = 0, right = 0
        while right < nums.count {
            var sum = 0
            for i in left...right {
                sum += nums[i]
            }

            if sum < target {
                right += 1
            } else {
                minLength = min(minLength, right - left + 1)
                left += 1
            }

            if left > right {
                right += 1
            }
        }
        return minLength == Int.max ? 0 : minLength
    }
}

优化后：

时间复杂度：O(n)，其中 n 是数组的长度。指针 left 和 right 最多各移动 n 次。
空间复杂度：O(1)。

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        var minLength = Int.max
        var left = 0, right = 0
        var sum = 0
        while right < nums.count {
            sum += nums[right]
            while sum >= target {
                minLength = min(minLength, right - left + 1)
                // 左指针右移一位
                sum -= nums[left]
                left += 1
            }
            // 右指针右移一位
            right += 1
        }
        return minLength == Int.max ? 0 : minLength
    }
}

[ShannonChenCHN]

76. 最小覆盖子串（难度困难）

2021.03.21 11:45 am ~ 12:30 pm 08:20 pm ~ 10:50 pm

解法：滑动窗口

具体思路参考题解：https://leetcode-cn.com/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k/
代码实现参考题解：https://leetcode.com/problems/minimum-window-substring/discuss/294874/Swift-Solution

时间复杂度：O(n)，其中 n 是字符串 s 的长度。指针 start 和 end 最多各移动 n 次。
空间复杂度：O(k)，其中其中 k 是字符串 t 中的字符串集合个数。

具体 case 分析

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

 
"(A)DOBECODEBANC"   左右指针都在第0位
"(AD)OBECODEBANC"   右指针右移一位
"(ADO)BECODEBANC"   ...
"(ADOB)ECODEBANC"   ...
"(ADOBE)CODEBANC"   ...
"(ADOBEC)ODEBANC"   全部涵盖，记录当前窗口位置和长度

"A(DOBEC)ODEBANC"   左指针后移一位，不再全部涵盖

"A(DOBECO)DEBANC"   右指针右移一位
"A(DOBECOD)EBANC"   ...
"A(DOBECODE)BANC"   ...
"A(DOBECODEB)ANC"   ...
"A(DOBECODEBA)NC"   右指针右移一位后，全部涵盖，记录当前窗口位置和长度

"AD(OBECODEBA)NC"   左指针后移一位后，依然全部涵盖，记录当前窗口位置和长度
"ADO(BECODEBA)NC"   ...
"ADOB(ECODEBA)NC"   ...
"ADOBE(CODEBA)NC"   ...
"ADOBEC(ODEBA)NC"   左指针后移一位，不再全部涵盖

"ADOBEC(ODEBAN)C"   右指针右移一位  
"ADOBEC(ODEBANC)"   右指针右移一位后，全部涵盖，记录当前窗口位置和长度
"ADOBECO(DEBANC)"   左指针后移一位后，依然全部涵盖，记录当前窗口位置和长度
"ADOBECOD(EBANC)"   左指针后移一位后，依然全部涵盖，记录当前窗口位置和长度
"ADOBECODE(BANC)"   左指针后移一位后，依然全部涵盖，记录当前窗口位置和长度

"ADOBECODEB(ANC)"   左指针后移一位，不再全部涵盖
"ADOBECODEB(ANC)"   右指针右移一位，越界

Swift 代码实现：

class Solution {
    func minWindow(_ s: String, _ t: String) -> String {
        // 为了方便处理，这里将字符串转成数组
        let charArray = Array(s) 

        // 用 map 去实时记录窗口涵盖目标字符的情况，如果某个字符对应的 value 为 0 
        // 说明窗口涵盖了该字符。
        // 为了更快捷地知道是否涵盖了所有目标字符，我们再单独维护一个标记
        var targetCount = t.count
        var map: [Character: Int] = [:]
        for c in t {
            if map[c] == nil {
                map[c] = 0
            }
            map[c] = map[c]! + 1
        }

        // 窗口滑动算法相关的逻辑
        var start = 0, end = 0
        var minStart = 0, minLength = Int.max
        while end < charArray.count {
            // 右指针右移前更新状态
            let currentChar = charArray[end]
            if map[currentChar] != nil { // 说明这个是目标字符
                if map[currentChar]! > 0 { // 为负数说明在窗口中有多余重复出现
                    targetCount -= 1
                }
                map[currentChar] = map[currentChar]! - 1
            }

            // 如果涵盖了所有的目标字符，就记录窗口位置，并移动左指针
            while targetCount == 0 {
                // 记录窗口位置
                if end - start + 1 < minLength {
                    minLength = end - start + 1
                    minStart = start
                }

                // 左指针右移前更新状态
                let startChar = charArray[start]
                if map[startChar] != nil { // 说明这个是目标字符
                    if map[startChar]! >= 0 { // 说明不是在窗口中有多余重复出现的
                        targetCount += 1
                    }
                    map[startChar] = map[startChar]! + 1
                }

                // 左指针右移一位
                start += 1
            }

            // 右指针右移一位
            end += 1
        }

        return minLength == Int.max ? "" : String(charArray[minStart..<minStart+minLength])
    }
}

[ShannonChenCHN]

239. 滑动窗口最大值 （难度困难）

注：本题同 剑指 Offer 59 - I. 滑动窗口的最大值

解法一：堆/优先队列

2021.03.25 10:45 am ~ 11:50 am

参考题解：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

思路：维护一个大根堆，初始时将数组中前 k 个元素添加到堆中进行堆化，堆顶元素即第一个窗口的最大值，然后窗口每次往右移动一位时，将新元素添加到堆中，然后 shift up，然后在一个 while 循环中判断堆顶元素是否还在窗口中，否则将堆顶元素移除掉。

时间复杂度：O(nlogn)，其中 nn 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。

空间复杂度：O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间，只计算额外的空间使用。

代码实现：

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        
        var heap = MaxHeap(nums, k) // 前 k 个建堆
        
        var result = [Int]()
        result.append(heap.peek().0)

        var start = 1
        var end = k
        while end < nums.count {
            heap.offer((nums[end], end))
            while heap.peek().1 < start { // 堆顶元素不在窗口中
                heap.poll()
            }
            result.append(heap.peek().0)
            start += 1
            end += 1
        }
        return result
    }
}

class MaxHeap {
    var nodes: [(Int, Int)] = [(Int, Int)]() // 保存的是 Tuple(值，数组中的位置)

    init(_ nums: [Int], _ k: Int) {
        for i in 0..<k {
            if i < nums.count {
                offer((nums[i], i))
            }
        }
    }

    func peek() -> (Int, Int) {
        return nodes.first!
    }

    func poll() {
        nodes[0] = nodes.removeLast()
        shiftDown()
    }

    func offer(_ data: (Int, Int)) {
        nodes.append(data)
        shiftUp()
    }

    func shiftUp() {
        var currentIndex = nodes.count - 1
        while currentIndex >= 1 {
            let parentIndex = (currentIndex - 1) / 2
            if nodes[currentIndex].0 > nodes[parentIndex].0 {
                nodes.swapAt(currentIndex, parentIndex)
                currentIndex = parentIndex
            } else {
                break
            }
        }
    }

    func shiftDown() {
        var currentIndex = 0
        while currentIndex < nodes.count {
            var maxIndex = currentIndex
            let leftChildIndex = currentIndex * 2 + 1
            let rightChildIndex = currentIndex * 2 + 2

            if leftChildIndex < nodes.count && nodes[leftChildIndex].0 > nodes[maxIndex].0 {
                maxIndex = leftChildIndex
            }

            if rightChildIndex < nodes.count && nodes[rightChildIndex].0 > nodes[maxIndex].0 {
                maxIndex = rightChildIndex
            }

            if maxIndex == currentIndex {
                break
            } else {
                nodes.swapAt(maxIndex, currentIndex)
                currentIndex = maxIndex
            }
        }
    }
}

解法二：单调(双端)队列

2021.03.27 04:50 pm ~ 06:20 pm

参考：

• 极客时间专栏：算法面试通关40讲
• LeetCode 官方题解

思路：基于滑动窗口的特点，除了在每次滑动窗口时，通过维护一个堆来算出最大值，我们还有一个更直接更高效的办法——单调队列。因为每次滑动窗口时，窗口中的最大值不一定在最左边，所以最大值左边的元素在后续的滑动中也不可能成为最大值了。基于此，我们可以在滑动窗口时，维护一个从大到小的单调队列，“出窗”的元素从左边出列，“入窗”的元素从右边加入时，加入新元素时，判断队列中左边的元素是否比它大，是则直接入列，否则将队列中左边的元素出列，重复这个比较过程，直到队列符合单调递减的特点。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

 滑动窗口的位置                 单调队列           最大值
---------------               ---------------   -----
[1  3  -1] -3  5  3  6  7     [3  -1]             3
 1 [3  -1  -3] 5  3  6  7     [3  -1  -3]         3
 1  3 [-1  -3  5] 3  6  7     [5]                 5
 1  3  -1 [-3  5  3] 6  7     [5  3]              5
 1  3  -1  -3 [5  3  6] 7     [6]                 6
 1  3  -1  -3  5 [3  6  7]    [7]                 7

时间复杂度：O(n)。n 为 nums 的元素个数，虽然有一个嵌套循环，但是实际上最坏的情况下也只是遍历数组之外，每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。
空间复杂度：O(k)。

代码实现：

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        
        var indexDeque = [Int]() // 记录索引的单调递减队列
        var result = [Int]()

        // 滑动窗口
        var startIndex = 0
        var endIndex = 0
        while endIndex < nums.count {
            // 维护队列
            if indexDeque.count > 0 && 
            indexDeque.first! < startIndex { // “出窗”
                indexDeque.removeFirst()
            }
            while indexDeque.count > 0 && 
            nums[indexDeque.last!] < nums[endIndex] { // 从后往前，删除比新元素小的元素
                indexDeque.removeLast()
            }
            indexDeque.append(endIndex) // “入窗”

            // 窗口开始滑动
            if endIndex >= k - 1 {
                // 记录结果
                result.append(nums[indexDeque.first!])
                startIndex += 1
            }
            endIndex += 1
        }

        return result
    }
}