跳到主要内容

双指针与滑动窗口

介绍​

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。

若两个指针指向同一数组，遍历方向相同且不会相交，则也称为 滑动窗口（两个指针包围的 区域即为当前的窗口），经常用于区间搜索。

若两个指针指向同一数组，但是遍历方向相反，则可以用来进行 搜索，待搜索的数组往往是排好序的。

滑动窗口​

对于大部分滑动窗口类型的题目，一般是考察字符串的匹配。比较标准的题目，会给出一个模式串B，以及一个目标串A。然后提出问题，找到A中符合对B一些限定规则的子串或者对A一些限定规则的结果，*最终*再将搜索出的子串完成题意中要求的组合或者其他

我们常用的解题思路，是去维护一个可变长度的滑动窗口。无论是使用双指针，还是使用双端队列，又或者用游标等其他奇技淫巧，目的都是一样的。

滑动窗口的处理步骤​

  • 第一步、确定初始位置

  • 第二步、right 右移，扩大窗口

  • 第三步、left 右移，收缩窗口

  • 第四部、状态记录

模板​

 class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 初始化状态
        visited = {} 
        for char in s:
            visited[char] = 0
        # 确定初始位置
        l, r = 0, -1 
        
        # 滑动窗口维护一个窗口集
        while (滑动窗口可以右移):
            if （可以右移）: # 右移
                r += 1
                visited[s[r]] = 1
            else: # 左移
                visited[s[l]] -= 1
                l += 1
            # 状态记录
            # ...
        return 状态

经典题型​

双指针​

滑动窗口是双指针的一个特殊情况。

当双指针位于首尾，共同相对移动的时候，就可以用来解决 搜索 问题