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


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

在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 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 的字母异位词的子串,返回这些子串的起始索引。

字符串只包含小写英文字母,并且字符串 sp 的长度都不超过 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;
    }
}

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 76 题:最小覆盖子串 「力扣」第 76 题:最小覆盖子串
「力扣」第 76 题:最小覆盖子串 中文网址:76. 最小覆盖子串 ; 英文网址:76. Minimum Window Substring 。 给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。 示
下一篇 
「力扣」第 461 题:汉明距离 「力扣」第 461 题:汉明距离
「力扣」第 461 题:汉明距离链接:https://leetcode-cn.com/problems/hamming-distance 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。 给出两个整数 x 和 y,计算
  目录