(滑动窗口)算法简介

滑动窗口,顾名思义,就是有一个大小可变的窗口,左右两端方向一致的向前滑动(右端固定,左端滑动;左端固定,右端滑动)。

可以想象成队列,一端在push元素,另一端在pop元素,如下所示:

1
2
3
4
5
6
7
8
假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动,则有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]

适用范围

  1. 一般是字符串或者列表
  2. 一般是要求最值(最大长度,最短长度等等)或者子序列

算法思想

  1. 在序列中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个窗口。
  2. 先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的序列符合要求。
  3. 此时,停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的序列不再符合要求。同时,每次增加 left前,都要更新一轮结果。
  4. 重复第 2 和第 3 步,直到 right 到达序列的尽头。
    思路其实很简单:第 2 步相当于在寻找一个可行解,然后第 3 步在优化这个可行解,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

算法模板

  1. 单层循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    def template():
    # 初始化滑动窗口两端
    left = right = 0

    # 序列及序列长度
    seq, seq_len = xx, xx

    # 滑动窗口序列
    slide_win = []

    # 结果值
    rst = xx

    while right < seq_len:
    slide_win.append(seq[right])
    # 还没找到一个可行解
    if not avaliable(slide_win):
    # 扩大窗口
    right += 1
    else:
    # 找到一个可行解,更新结果值
    rst = update()
    # 缩小窗口
    left += 1
  2. 双层循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def template():
    # 初始化滑动窗口两端
    left = right = 0

    # 序列及序列长度
    seq, seq_len = xx, xx

    # 滑动窗口序列
    slide_win = []

    # 结果值
    rst = xx

    while right < seq_len:
    slide_win.append(seq[right])
    # 还没找到一个可行解
    if not avaliable(slide_win):
    # 扩大窗口
    right += 1
    continue

    # 循环更新可行解
    while avaliable(slide_win):
    # 找到一个可行解,更新结果值
    rst = update()
    # 缩小窗口
    left += 1

3. 无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

  1. 示例 1:

    1
    2
    3
    输入: s = "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3
  2. 示例 2:

    1
    2
    3
    输入: s = "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1
  3. 示例 3:

    1
    2
    3
    输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
  4. 示例 4:

    1
    2
    输入: s = ""
    输出: 0
  • 提示:

    1
    2
    0 <= s.length <= 5 * 104
    s 由英文字母、数字、符号和空格组成

思路

滑动窗口

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var lengthOfLongestSubstring = function(s) {
// 哈希集合,记录每个字符是否出现过
const occ = new Set();
const n = s.length;
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
let rk = -1, ans = 0;
for (let i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格,移除一个字符
occ.delete(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
};

567. 字符串的排列

给你两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。

换句话说 s1 的排列之一是 s2 的子串。

  1. 示例 1:

    1
    2
    3
    输入:s1 = "ab" s2 = "eidbaooo"
    输出:true
    解释:s2 包含 s1 的排列之一 ("ba").
  2. 示例 2:

    1
    2
    输入:s1= "ab" s2 = "eidboaoo"
    输出:false
  • 提示:

    1
    2
    1 <= s1.length, s2.length <= 104
    s1 和 s2 仅包含小写字母

思 路

由于排列不会改变字符串中每个字符的个数,所以只有当两个字符串每个字符的个数均相等时,一个字符串才是另一个字符串的排列。

根据这一性质,记 s1的长度为 nn,我们可以遍历 s2中的每个长度为 nn 的子串,判断子串和 s1中每个字符的个数是否相等,若相等则说明该子串是s1的一个排列。

使用两个数组 cnt1cnt2cnt1统计 s1中各个字符的个数,cnt2统计当前遍历的子串中各个字符的个数。

由于需要遍历的子串长度均为 nn,我们可以使用一个固定长度为 nn 的滑动窗口来维护 cnt2:滑动窗口每向右滑动一次,就多统计一次进入窗口的字符,少统计一次离开窗口的字符。然后,判断 cnt1是否与 cnt2相等,若相等则意味着 s1的排列之一是 s2的子串。

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var checkInclusion = function(s1, s2) {
const n = s1.length, m = s2.length;
if (n > m) {
return false;
}
const cnt1 = new Array(26).fill(0);
const cnt2 = new Array(26).fill(0);
for (let i = 0; i < n; ++i) {
++cnt1[s1[i].charCodeAt() - 'a'.charCodeAt()];
++cnt2[s2[i].charCodeAt() - 'a'.charCodeAt()];
}
if (cnt1.toString() === cnt2.toString()) {
return true;
}
for (let i = n; i < m; ++i) {
++cnt2[s2[i].charCodeAt() - 'a'.charCodeAt()];
--cnt2[s2[i - n].charCodeAt() - 'a'.charCodeAt()];
if (cnt1.toString() === cnt2.toString()) {
return true;
}
}
return false;
};