• 完成两道滑动窗口的 mid 题目
• 把 js 的基础知识看完了
• 浅学了 vue 相关知识

滑动窗口

也是双指针的一种类型，同向双指针

无重复字符的最长子串

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

思路分析

由于我们都要接到一个没有重复元素的子串后面，所以重复的元素一定来自于接入的字符，所以我们使用滑动窗口来进行处理 使用哈希表来去重，以下是代码实现

使用哈希集合（布尔数组）

class Solution {  
    public int lengthOfLongestSubstring(String S) {  
        char[] s = S.toCharArray();  
        int n = s.length;  
        int ans = 0, left = 0;  
        boolean[] has = new boolean[128];  
        for (int right = 0; right < n; right++) {  
            char c = s[right];  
            while (has[c]) {   // 去重 在表中查询到了重复的字母，执行以下
                has[s[left]] = false;   // 移除重复字母 
                left++;       // 移动窗口
            }  
            has[c] = true;  
            ans = Math.max(ans, right - left +1 );  
        }  
        return ans;  
    }  
}

使用哈希表

class Solution {  
    public int lengthOfLongestSubstring(String S) {  
        char[] s = S.toCharArray(); // 转换成 char[] 加快效率（忽略带来的空间消耗）  
        int n = s.length;  
        int ans = 0;  
        int left = 0;  
        int[] cnt = new int[128]; // 也可以用 HashMap<Character, Integer>，这里为了效率用的数组  
        for (int right = 0; right < n; right++) {  
            char c = s[right];  
            cnt[c]++;  
            while (cnt[c] > 1) { // 窗口内有重复字母  
                cnt[s[left]]--; // 移除窗口左端点字母  
                left++; // 缩小窗口  
            }  
            ans = Math.max(ans, right - left + 1); // 更新窗口长度最大值  
        }  
        return ans;  
    }  
}

定长滑窗

窗口右端点在 i 时，由于窗口长度为 k，所以窗口左端点为 i−k+1 所以对于订餐滑窗的题目，我们总结为以下步骤 1. 首先 下标为 i 的元素进入窗口，更新相关统计量。如果左端点 i-k+1 < 0 则证明 第一个窗口还没有形成，不断重复第一步直至形成窗口 2. 更新答案 3. 左端点离开窗口，更新相关统计量，进行下一个循环

我们由一道题目进行引入

定长子串中元音的最大数目

给你字符串 s 和整数 k 。 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为（a, e, i, o, u）。

class Solution {  
    public int maxVowels(String S, int k) {  
        char[] s = S.toCharArray();  
        int ans = 0;  
        int vowel = 0;  
        for (int i = 0; i < s.length; i++) {  // 开始枚举 窗口的右端点
        // 更新相关统计数据
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u' ) {  
                vowel++;  
            }  
            int left = i - k + 1;  // 左端点
            if (left < 0) {  // 窗口大小不足 k
                continue;    // 回到开头，直到行成第一个窗口
            }  
            ans = Math.max(ans, vowel);  // 更新答案
            if (ans == k) {              // 如果 ans 等于 窗口最大值 
                break;                   // 即已经为答案理论最大值，停止循环
            }  
  
            char out = s[left];   // 左端点离开窗口 
            if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {  
                vowel--;    // 离开窗口也要更新一下统计数据
            }  
        } return ans;  
    }  
}

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

思路

在有了定长窗口的思路后，我们可以用这一道题的思路来解答这道题目（也可以用不定长滑窗思路）

如果窗口内字母出现的次数跟 p 中一样，意味着他们是异位词，直接将左端点的下标加入答案即可 看代码注释

解答

定长滑窗

时间复杂度：O(∣Σ∣m+n)

class Solution {  
    public List<Integer> findAnagrams(String s, String p) {  
	    // 统计 p 的每种字母出现的次数
        int[] cntP = new int[26]; 
        for (char c : p.toCharArray()) {  
            cntP[c - 'a']++;  // 统计字母
        }  
  
        List<Integer> ans = new ArrayList<>();  // 新建返回答案的列表
        int[] cntS = new int[26];  // 用来统计 s 字母出现的次数
        for (int right = 0; right < s.length(); right++) {  
            cntS[s.charAt(right) - 'a']++;  // 右端点字母进入窗口 + 更新数据
            int left = right - p.length() + 1;  
            if (left < 0) {  // 窗口长度不足
                continue;  
            }  
            if (Arrays.equals(cntS, cntP)) {  // 对比子串和 p 字母出现的次数相同
                ans.add(left);                // 将左端点的下标添加至答案里
            }  
            cntS[s.charAt(left) - 'a']--;     // 移动左端点（离开窗口 + 更新数据
        }  
        return ans;  
    }  
}

不定长滑窗

我不行了，不定长的做法明天写我要看别的去了 我又行了现在写 该解法与定长思路差不多一致 时间复杂度：O(m+n)

class Solution {  
    public List<Integer> findAnagrams(String s, String p) {  
        int[] cnt = new int[26];  // 统计 p 中的字母出现次数
        for (char c : p.toCharArray()) {  
            cnt[c - 'a']++;  
        }  
  
        List<Integer> ans = new ArrayList<>();  
        int left = 0;  
        for (int right = 0; right < s.length(); right++) {  
            int c = s.charAt(right) - 'a';  
            cnt[c]--;   // 右端点进入窗口
            while (cnt[c] < 0) {  // 字母 c 太多了 要移动窗口
                cnt[s.charAt(left) - 'a']++;  // 左端点移动
                left++;  
            }  
            if (right - left + 1 ==p.length()) {  // 子串和 p 字母出现次数一致
                ans.add(left);                    // 下标添加至答案
            }  
        }  
        return ans;  
    }  
}