LeetCode Hot 100：滑动窗口

Leetcode Hot 100

滑动窗口

无重复字符的最长子串

• 链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

• 题目：求不含有重复字符的最长子串的长度。比如：abcabcbb是abc，bbbbb是b，pwwekw是wek

• 解决：

  • 滑动窗口：循环遍历字符串，每次左指针向右移动一位；每次循环移动右指针，直到出现重复字符。（原理：右指针肯定是递增的）

    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

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

• 链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

• 题目：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词（字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。） 的子串，返回这些子串的起始索引。比如：s = “abab”, p = “ab”，返回[0,1,2]；s = “cbaebabacd”, p = “abc”，返回[0, 6]。

• 解决：

  • 滑动窗口：

    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length(), pLen = p.length();
            if (sLen < pLen) {
                return new ArrayList<Integer>();
            }
            List<Integer> ans = new ArrayList<Integer>();
            int[] sCount = new int[26];//s中字符数
            int[] pCount = new int[26];//p中字符数
            for (int i = 0; i < pLen; ++i) {
                ++sCount[s.charAt(i) - 'a'];
                ++pCount[p.charAt(i) - 'a'];
            }
            if (Arrays.equals(sCount, pCount)){//当前窗口中字符数相等，则符合要求
                ans.add(0);
            }
            for (int i = 0; i < sLen - pLen; ++i) {//收缩窗口
                --sCount[s.charAt(i) - 'a'];//去掉左端点
                ++sCount[s.charAt(i + pLen) - 'a'];//加入右端点
                if (Arrays.equals(sCount, pCount)) {
                    ans.add(i + 1);
                }
            }
            return ans;
        }
    }

  • 滑动窗口（优化）：维护滑动窗口，窗口长度固定为p的长度，比较窗口里面的字符是否符合要求（通过count数组存储不同，differ维护不同的个数，differ为0则相同）。

    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {//s长度小于p，肯定不符合
            return new ArrayList<Integer>();
        }
        
        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {//count存储长度为pLen的窗口中，s和p字符的差别
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }
    
        int differ = 0;
        for (int j = 0; j < 26; ++j) {//differ存储哪些字符存在差异
            if (count[j] != 0) {
                ++differ;
            }
        }
    
        if (differ == 0) {//如果differ为0，说明没有字符存在差异，符合字母异位词
            ans.add(0);
        }
    
        for (int i = 0; i < sLen - pLen; ++i) {
            //移除下标为i的字符
            if (count[s.charAt(i) - 'a'] == 1) {//窗口中字母s[i]的数量与字符串p中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {//窗口中字母s[i]的数量与字符串p中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];
    
            //加入下标为i+pen的字符
            if(count[s.charAt(i+pLen)-'a'] == -1){//窗口中字母 s[i+pLen] 的数量与字符串p中的数量从不同变得相同
                --differ;
            }else if(count[s.charAt(i+pLen)-'a'] == 0){//窗口中字母 s[i+pLen] 的数量与字符串p中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];
    
            if (differ == 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }