算法——滑动窗口（Sliding Window）

雨点打透心脏的1/2处 2024-02-18 13:28 69阅读 0赞

## 一、背景知识 ##

>  *  **滑动窗口算法（Sliding Window）**：
>     
>      *  在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。
>      *  ![bce166f154f847b99cfffdd8fc7d8602.png][]
>      *  题型一：固定长度
>      *  题型二：不固定长度

## 二、例题 ##

### 1、无重复字符的最长子串（不定长度） ###

![44c46e748941409c8978ee95b870bd1f.png][]

写法一： 我的答案

class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(s.length()==0){
                return 0;
            }
            int l=0;//左指针
            int r=0;//右指针
            int maxLen=1;
            List<Character> list=new ArrayList<>();
            while(r<s.length() && l<s.length()){
                if(!list.contains(s.charAt(r))){
                    list.add(s.charAt(r));//窗口右侧扩张
                    maxLen=Math.max(maxLen,r-l+1);//维护一个子串长度的最大值
                    r++;
                }else{
                    int index=list.indexOf(s.charAt(r));//在窗口里查找被重复的字符的下标
                    delItems(index,list);//把重复字符及其以前的字符移出窗口
                    l=l+index+1;//窗口左侧收缩
                }
            }
            return maxLen;
        }
        //
        public void delItems(int end,List list){
            while(end>=0){//从后往前删
                list.remove(end);
                end--;
            }
        }
    }

![d465a70cd7bd4bdf87445db293667a16.png][]![70c521b8492643db812724be585d00c7.jpeg][]

写法二： 官方答案

> 外循环（for）枚举字符串s的所有字符，当作滑动窗口的左边界，进入内循环（while）后，不断往右移，直到遇到重复的字符后，跳出内循环。
> 
> 更新最长子串长度，删除滑动窗口最左边的一个元素。
> 
> 如果该元素不是被重复的元素，就不会再次进入内循环，而是一直在外循环徘徊，一个接一个地删掉滑动窗口最左边的元素，直到删掉那个被重复的元素

class Solution {
        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 个字符是一个极长的无重复字符子串
                // rk-i+1为当前滑动窗口内的子串长度
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
    }

![be7e28363d4b4b829e335370c29e7ff6.png][]

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

![363ec6e1e3994259b1ff4c38692d654f.png][]

> 该题用排序法会超时，用链表或哈希表会超出内存限制

写法一：

> 突破点：
> 
> 在字符串 s中构造一个长度为与字符串 p的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；**当窗口中每种字母的数量与字符串 p中每种字母的数量相同时**，则说明当前窗口为字符串 p的异位词。

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length(), pLen = p.length();
    
            //当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词
            if (sLen < pLen) {
                return new ArrayList<Integer>();
            }
    
            List<Integer> ans = new ArrayList<Integer>();
            int[] sCount = new int[26];//计算字符串s中26个字母出现的个数
            int[] pCount = new int[26];//计算字符串p中26个字母出现的个数
            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) {//用滑动窗口遍历字符串s
                --sCount[s.charAt(i) - 'a'];//滑动窗口左边界收缩，sCount数组里该字母的个数减1
                ++sCount[s.charAt(i + pLen) - 'a'];//滑动窗口右边界扩张，sCount数组里该字母的个数加1
    
                if (Arrays.equals(sCount, pCount)) {//找到异位词
                    ans.add(i + 1);
                }
            }
    
            return ans;
        }
    }

[bce166f154f847b99cfffdd8fc7d8602.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/3413c1f510454c7aac69c8ebfddc4dc4.png
[44c46e748941409c8978ee95b870bd1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/1e309711b4404e27a45df8d7d2b90a5c.png
[d465a70cd7bd4bdf87445db293667a16.png]: https://img-blog.csdnimg.cn/d465a70cd7bd4bdf87445db293667a16.png
[70c521b8492643db812724be585d00c7.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/3b3c96e8f3034d00a9d9f5d1bd261347.png
[be7e28363d4b4b829e335370c29e7ff6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/2c93ff793c014349bb1528312bc33431.png
[363ec6e1e3994259b1ff4c38692d654f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/34e139cc959940889982af8cbcf359ea.png