NOTES · 学习笔记

找到字符串中所有字母异位词:固定窗口,逐格滑动

LeetCode滑动窗口 · 中等约 4 分钟

题目

这道题我们可以用滑动窗口来解决。先分析思路,我们看示例一:输入 s = "cbaebabacd",p = "abc",输出 [0,6]。

我们要从 s 这个字符串中找到所有 p 的字母异位词子串,p 是我们的目标,最后输出它们的起始下标。

那么我们首先定义一个窗口,窗口的大小就规定为 p 的长度。比如示例一中 p 的长度为 3,那么我们的窗口大小就是 3。

定义好窗口后,我们就要解决如何判断窗口中的字符是不是 p 的字母异位词,那么我们需要两个指针,一个左指针指向初始第一个元素,第二个右指针指向当前窗口中最后一个元素。

例如,s = "cbaebabacd",p = "abc",窗口大小为 3:left = 0,指向 c;right = 2,指向 a。当前窗口就是 "cba"。

那么,我们如何判断当前窗口是不是字母异位词呢?我们可以定义两个长度为 26 的数组,分别用来统计 p 和当前窗口中每个字母出现的次数。

因为题目中只有小写英文字母,所以可以用数组的下标对应字母,比如 a 对应 0,b 对应 1,以此类推。

统计完成后,我们只需要比较两个数组是否相等。一个数组统计 p,一个数组统计 s 的当前窗口。如果相等,说明两个字符串中的字母及其出现次数都相同,那么当前窗口就是一个字母异位词。

当前窗口是 "cba",它和 p = "abc" 中的字母及出现次数相同,所以这是一个字母异位词。我们定义一个 res 数组,用来保存异位词的起始下标,也就是 0。

接下来,我们开始移动窗口。首先移除左指针指向的元素 c,然后左指针向右移动一格。接着右指针也向右移动一格,并将新进入窗口的元素加入窗口。

每次移动后,我们都要判断当前窗口是不是字母异位词。如果是,就将当前左指针的下标保存到 res 数组中。一直重复这个过程,直到遍历完整个字符串。

func findAnagrams(s string, p string) []int {
    left := 0               // 定义左指针
    right := len(p) - 1     // 定义右指针
    var pCount [26]int      // 统计 p 中每个字母出现的次数
    var window [26]int      // 统计当前窗口中每个字母出现的次数
    if len(p) > len(s) {
        return nil          // 目标字符串比 s 长,不可能找到符合条件的子串
    }
    for i := 0; i < len(p); i++ {
        pCount[p[i]-'a']++  // 统计 p 中每个字母出现的次数
    }
    for i := 0; i < len(p); i++ {
        window[s[i]-'a']++  // 统计初始窗口中每个字母出现的次数
    }
    res := []int{}          // 保存字母异位词的起始下标
    if window == pCount {
        res = append(res, left) // 初始窗口符合条件时,保存左下标
    }
    for right < len(s)-1 {
        window[s[left]-'a']--  // 移除窗口最左边的字母
        left++                 // 左指针向右移动一格
        right++                // 右指针向右移动一格
        window[s[right]-'a']++ // 把新进入窗口的字母计入统计
        if window == pCount {
            res = append(res, left) // 当前窗口符合条件时,保存左下标
        }
    }
    return res
}