「滑动窗口」专题：概述与经典问题

「滑动窗口」专题 ：滑动窗口的基本思想

在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 right 指针，和一个用于收缩窗口的 left 指针。在任意时刻，只有一个指针运动，而另一个保持静止。

「滑动窗口」的问题其实思想并不难，但是在有一定的编码量，如果一不小心还有可能出错。在这里解决边界问题的一个小技巧，就是所谓的「循环不变量」。在这里再和大家总结一下：

• 这里「循环不变量」的定义是一个空区间（如果不是空区间，也要满足定义）；
• 这个区间一开始的时候是一个空区间；
• 在遍历的过程中，维持循环不变量的定义；
• 在遍历完成以后，滑动窗口完成了所有可能的情况而不会错过最优解。

需要使用一些变量去描述「滑动窗口」内元素的性质，这里需要根据具体问题具体设计。

对于一个固定的左端点，满足条件的右端点的集合是连续的，但是题目只要我们求最值。

右端点主动，左端点被动。

例 1：「力扣」第 3 题：无重复字符的最长子串（滑动窗口典型问题）

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

Java 代码：

public class Solution {

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len < 2) {
            return len;
        }

        char[] charArray = s.toCharArray();
        // 描述 [left, right) 里是否有元素的变量
        int[] hashMap = new int[128];
        // [left, right) 无重复的元素
        int res = 1;
        for (int left = 0, right = 0; right < len; right++) {
            hashMap[charArray[right]]++;
            if (hashMap[charArray[right]] == 2) {
                while (hashMap[charArray[right]] == 2) {
                    hashMap[charArray[left]]--;
                    left++;
                }
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

例 2：「力扣」第 76 题：最小覆盖子串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

Java 代码：

public class Solution {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0) {
            return "";
        }

        int[] countS = new int[256];
        int[] countT = new int[256];
        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int distance = 0;
        for (char charT : charArrayT) {
            if (countT[charT] == 0) {
                distance++;
            }
            countT[charT]++;
        }

        int minLen = sLen + 1;
        int left = 0;
        int right = 0;
        int count = 0;
        int begin = 0;
        while (right < sLen) {
            if (countT[charArrayS[right]] == 0) {
                right++;
                continue;
            }

            countS[charArrayS[right]]++;
            if (countS[charArrayS[right]] == countT[charArrayS[right]]) {
                count++;
            }
            right++;

            while (count == distance) {
                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }

                if (countT[charArrayS[left]] > 0) {
                    countS[charArrayS[left]]--;
                    if (countS[charArrayS[left]] < countT[charArrayS[left]]) {
                        count--;
                    }
                }
                left++;
            }
        }

        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        String minWindow = solution.minWindow(S, T);
        System.out.println(minWindow);
    }
}

例 3：第 438 题：找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

Java 代码：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        List<Integer> res = new ArrayList<>();
        if (sLen == 0 || pLen == 0) {
            return res;
        }

        int[] text = new int[128];
        int[] pattern = new int[128];

        char[] charArrayP = p.toCharArray();
        int distance = 0;
        for (char c : charArrayP) {
            if (pattern[c] == 0) {
                distance++;
            }
            pattern[c]++;
        }

        int left = 0;
        int right = 0;
        int count = 0;
        char[] charArrayS = s.toCharArray();
        while (right < sLen) {
            if (pattern[charArrayS[right]] > 0) {
                text[charArrayS[right]]++;
                if (text[charArrayS[right]] == pattern[charArrayS[right]]) {
                    count++;
                }
            }

            right++;
            while (count == distance) {
                if (right - left == pLen) {
                    res.add(left);
                }

                if (pattern[charArrayS[left]] > 0) {
                    text[charArrayS[left]]--;
                    if (text[charArrayS[left]] < pattern[charArrayS[left]]) {
                        count--;
                    }
                }
                left++;
            }
        }
        return res;
    }
}

（本节完）