03_滑动窗口

LeetCode Hot 100

---

3. 无重复字符的最长子串

难度：中等 | LeetCode 链接

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

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路

使用滑动窗口维护一个不含重复字符的区间 [left, right]。当右指针遇到重复字符时，移动左指针直到窗口内无重复。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //使用滑动窗口
        Set<Character> set = new HashSet<>();
        int length = s.length();
        int lPointer = 0;
        int ans = 0;
        for(int rPointer = 0;rPointer<length;rPointer++) {
            //移动右指针，添加字符
            Character c = s.charAt(rPointer);
            while(set.contains(c)){
                //如果集合包含字符，移动左指针移，除左指针所在位置字符，直到移除掉重复字符
                set.remove(s.charAt(lPointer));
                lPointer++;
            }
            set.add(c);
            //记录最大值
            ans = Math.max(ans,rPointer-lPointer+1);
        }
        return ans;
    }
}

复杂度：时间 O(n)，空间 O (min (m, n)) 其中 m 是字符集大小。比如英文字母最多 26 个，ASCII 字符最多 128 个

---

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

难度：中等 | LeetCode 链接

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

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。

思路

把 p 映射为频次数组， 维护固定长度为 p.length() 的滑动窗口，在 s 上移动，统计窗口内字符频次与 p 的频次进行比较。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //把字符串p映射成0~25的数组上分别对应a~z
        int[] pCnt = new int[26];
        for(int i = 0;i<p.length();i++){
            pCnt[p.charAt(i) - 'a'] ++ ; //如：a-a =0 ,b-a = 1 
        }
        //同理把滑动窗口也映射到数组上
        int[] wCnt = new int[26];
        List<Integer> res = new ArrayList<>();
        for(int r = 0;r<s.length();r++){
            int l = r - p.length() + 1;
            //记录字符
            wCnt[s.charAt(r) - 'a'] ++;
            //窗口需要和p长度一致
            if(r<p.length()-1){
                continue;
            }
            //比较两个数组是否相同
            if(Arrays.equals(pCnt,wCnt)){
                res.add(l);
            }
            //继续寻找
            //左指针移动，恢复现场
            wCnt[s.charAt(l) - 'a'] --;
        }
        return res;
    }
}

复杂度：时间 O(n)，空间 O(1)

---

239. 滑动窗口最大值

难度：困难 | LeetCode 链接

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。返回每个窗口中的最大值。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

思路

使用单调队列（递减）。队头始终是当前窗口最大值。窗口移动时，移除过期元素并保持队列单调性。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //双端队列实现（队列最左边为最大元素） 左->右 （队首->队尾）
        //维护方法：及时弹出小于队尾的元素，保证双端队列有序
        Deque<Integer> q = new ArrayDeque<>();
        //一个有 nums.length - k +1 个窗口
        int[] ans = new int[nums.length-k+1];
        for(int i =0;i<nums.length;i++){
            //入队
            //过滤小于队尾的元素
            while(!q.isEmpty()&&nums[q.getLast()]<=nums[i]){
                q.removeLast();
            }
            q.addLast(i);
            //出队
            //如果队首元素超出了这个滑动窗口（即 小于 i -k +1）移除队首元素
            if(q.getFirst()<i-k+1){
                q.removeFirst();
            }
            //记录最大值
            if(i>=k-1){
                ans[i-k+1] = nums[q.getFirst()];
            }
        }
        return ans;
    }
}

复杂度：时间 O(n)，空间 O(k)

---

76. 最小覆盖子串

难度：困难 | LeetCode 链接

给你一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

思路

滑动窗口统计 t 中字符需求。右指针扩展满足需求后，左指针尽量收缩以缩小窗口，并记录最短区间。

代码

class Solution {
    //字符串不连续的情况
    public String minWindow(String s, String t) {
        int[] tCharArr = new int[128];

        //初始化
        for(int i=0;i<t.length();i++){
            char c = t.charAt(i);
            tCharArr[c]++;
        }
        int[] ansCharArr = new int[128];
        int l = 0;
        int ansL = -1;
        int ansR = s.length();
        for(int r=0;r<s.length();r++){
            char c = s.charAt(r);
            ansCharArr[c]++;
            //判断是否覆盖
            while(isCovered(tCharArr,ansCharArr)){
                //判断最小子字符串是否缩短
                if(r-l<ansR-ansL){
                    //记录边界
                    ansL = l;
                    ansR = r;
                }
                //删除最左边元素
                ansCharArr[s.charAt(l)]--;
                //左边界向右移动
                l++;
            }
        }
        return ansL < 0 ? "":s.substring(ansL,ansR+1);
    }

    private boolean isCovered(int[] tCharArr,int[] ansCharArr){
        //逐个字符比较大小
        for(int i='A';i<='Z';i++){
            //ans是长字符串 t是短字符串
            if(ansCharArr[i]<tCharArr[i]){
                return false;
            }
        }
        for(int i='a';i<='z';i++){
            //ans是长字符串 t是短字符串
            if(ansCharArr[i]<tCharArr[i]){
                return false;
            }
        }
        return true;
    }
}

复杂度：时间 O(n)，空间 O(1)

---