1、定义

在算法中，滑动窗口（Sliding Window）是一种常见的技术，用于处理连续序列数据或数组的问题。它基于定义一个固定大小的窗口，并通过在数据或数组上移动该窗口来解决问题。
滑动窗口算法通常用于处理串行数据（如字符串）或线性数据结构（如数组、链表）。它可以有效地解决一些需要对连续子序列进行操作或计算的问题，如子数组的最大/最小值、子字符串的最长/最短长度等。
滑动窗口算法的基本思想是，通过调整窗口的起始位置和结束位置，来处理连续的子序列。通常，窗口的大小是固定的，它可以是一个固定长度的区间，也可以是一个移动窗口，不断调整大小。

算法的一般步骤如下：

  1. 初始化窗口的起始位置和结束位置，使其覆盖待处理的初始序列。
  2. 计算窗口内部的结果（例如求和、求平均值、找到最大/最小值等）。
  3. 移动窗口，调整起始位置和结束位置，使其向右滑动一个位置。
  4. 重复步骤2和步骤3，直到窗口滑动到序列的末尾或满足特定的终止条件。

    通过不断调整窗口的位置，滑动窗口算法可以在线性时间复杂度内解决很多问题，而无需显式地枚举所有可能的子序列。它在处理大规模数据时具有较高的效率，并且常常用于解决字符串处理、数组操作和数据流处理等问题。

2、无重复字符的最大字串

利用map，来判断字符是否重复，作用就是改变左边界的值来达到控制窗口的目的

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         if (s.length() == 0) {
  4.             return 0;
  5.         }
  6.         HashMap<Character, Integer> hashMap = new HashMap<>();
  7.         int left = 0; // 定义起始位置，结束位置默认数组结尾
  8.         int res=0;
  9.         for (int i = 0; i < s.length(); i++) {
  10.             if (hashMap.containsKey(s.charAt(i))) {
  11.                 left = Math.max(left, hashMap.get(s.charAt(i)) + 1);
  12.                 //通过是否重复来确定边界的值
  13.             }
  14.             hashMap.put(s.charAt(i), i);
  15.             res = Math.max(res, i - left + 1);
  16.         }
  17.         return res;
  18.     }
  19. }

3、字符串中所有字母异位词

最low版：

通过排序来判断是否为字母异位词

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         ArrayList<Integer> list = new ArrayList<>();
  4.         if (s.length() < p.length() || p.length() == 0) {
  5.             return list;
  6.         }
  7.         char[] chars = p.toCharArray();
  8.         Arrays.sort(chars);
  9.         p = new String(chars);
  10.         for (int i = 0; i < s.length() - p.length()+1; i++) {
  11.             System.out.println(i);
  12.             System.out.println(p.length());
  13.             char[] temp = s.substring(i, i+p.length()).toCharArray();
  15.             Arrays.sort(temp);
  17.             String s1 = new String(temp);
  19.             if (s1.equals(p)) {
  20.                 list.add(i);
  21.             }
  22.         }
  23.         return list;
  24.     }
  25. }

优化版：

通过辅助数组记录字串出现的频次

  1.     public List<Integer> findAnagrams(String s, String p) {
  2.         int sLen = s.length(), pLen = p.length();
  4.         if (sLen < pLen) {
  5.             return new ArrayList<Integer>();
  6.         }
  8.         List<Integer> ans = new ArrayList<Integer>();
  9.         int[] sCount = new int[26];
  10.         int[] pCount = new int[26];
  11.         for (int i = 0; i < pLen; ++i) {
  12.             ++sCount[s.charAt(i) - 'a'];
  13.             ++pCount[p.charAt(i) - 'a'];
  14.         }
  16.         if (Arrays.equals(sCount, pCount)) {
  17.             ans.add(0);
  18.         }
  20.         for (int i = 0; i < sLen - pLen; ++i) {
  21.             --sCount[s.charAt(i) - 'a'];
  22.             ++sCount[s.charAt(i + pLen) - 'a'];
  24.             if (Arrays.equals(sCount, pCount)) {
  25.                 ans.add(i + 1);
  26.             }
  27.         }
  29.         return ans;
  30.     }

优化进阶：

  1. public List<Integer> findAnagrams(String s, String p) {
  2.     int[] cnt = new int[128]; // 统计字符频率的数组，ASCII码范围为0-127
  3.     for (char c : p.toCharArray()) {
  4.         cnt[c]++; // 统计p中每个字符出现的次数
  5.     }
  7.     int lo = 0, hi = 0; // 滑动窗口的起始和结束位置
  8.     List<Integer> res = new ArrayList<>(); // 存储结果的列表
  9.     while (hi < s.length()) {
  10.         if (cnt[s.charAt(hi)] > 0) {
  11.             cnt[s.charAt(hi)]--; // 将窗口内字符频率减1
  12.             if (hi - lo + 1 == p.length()) {
  13.                 res.add(lo); // 当窗口长度与p长度相等时，说明找到了一个anagram
  14.             }
  15.             hi++; // 扩展窗口的右边界
  16.         } else {
  17.             cnt[s.charAt(lo)]++; // 将窗口内最左侧字符频率加1，缩小窗口
  18.             lo++; // 缩小窗口的左边界
  19.         }
  20.     }
  22.     return res; // 返回结果列表
  23. }

该算法通过维护一个大小为128的数组cnt来统计字符频率，其中索引代表字符的ASCII码值。 循环遍历字符串p，将p中每个字符的频率存储到cnt数组中。 使用两个指针lo和hi来构建滑动窗口，初始化为0。 在while循环中，如果当前字符在cnt数组中的频率大于0，则说明该字符在p中存在，将该字符频率减1，并根据窗口长度判断是否找到了一个anagram。 如果当前字符在cnt数组中的频率等于0，说明该字符不在p中，需要缩小窗口，将窗口最左侧字符频率加1，并移动窗口左边界lo。 不断移动窗口的右边界hi，直到hi达到字符串s的长度为止。 返回存储结果的列表res，其中存储了所有找到的anagram的起始索引。