有点难度，几道和「滑动窗口」有关的算法面试题

红太狼 2022-04-24 09:56 272阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

## 前言科普：什么是滑动窗口算法    ##

滑动问题包含一个滑动窗口，它是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。

假设有数组 \[a b c d e f g h \]，一个大小为 3 的 **滑动窗口** 在其上滑动，则有：

[a b c]
      [b c d]
        [c d e]
          [d e f]
            [e f g]
              [f g h]

一般情况下就是使用这个窗口在数组的 **合法区间** 内进行滑动，同时 **动态地** 记录一些有用的数据，很多情况下，能够极大地提高算法地效率。

## 1. 滑动窗口最大值 ##

题目来源于 LeetCode 上第 239 号问题：滑动窗口最大值。题目难度为 Hard，目前通过率为 40.5% 。

### 题目描述 ###

给定一个数组 *nums*，有一个大小为 *k* 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 *k* 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

**示例:**

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
    输出: [3,3,5,5,6,7] 
    解释: 
    
      滑动窗口的位置                最大值
    ---------------               -----
    [1  3  -1] -3  5  3  6  7       3
     1 [3  -1  -3] 5  3  6  7       3
     1  3 [-1  -3  5] 3  6  7       5
     1  3  -1 [-3  5  3] 6  7       5
     1  3  -1  -3 [5  3  6] 7       6
     1  3  -1  -3  5 [3  6  7]      7

### 题目解析 ###

利用一个 **双端队列**，在队列中存储元素在数组中的位置， 并且维持队列的严格递减,，也就说维持队首元素是 **最大的** ，当遍历到一个新元素时, 如果队列里有比当前元素小的，就将其移除队列，以保证队列的递减。当队列元素位置之差大于 k，就将队首元素移除。

### 什么是双端队列（Dqueue） ###

Deque 的含义是 “double ended queue”，即双端队列，它具有队列和栈的性质的数据结构。顾名思义，它是一种前端与后端都支持插入和删除操作的队列。

Deque 继承自 Queue（队列），它的直接实现有 ArrayDeque、LinkedList 等。

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif] 动画描述 Made by Jun Chen

### 代码实现 ###

class Solution {
        
       public int[] maxSlidingWindow(int[] nums, int k) {
        
            //有点坑，题目里都说了数组不为空，且 k > 0。但是看了一下，测试用例里面还是有nums = [], k = 0，所以只好加上这个判断
            if (nums == null || nums.length < k || k == 0) return new int[0];
            int[] res = new int[nums.length - k + 1];
            //双端队列
            Deque<Integer> deque = new LinkedList<>();
            for (int i = 0; i < nums.length; i++) {
        
                //在尾部添加元素，并保证左边元素都比尾部大
                while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
        
                    deque.removeLast();
                }
                deque.addLast(i);
                //在头部移除元素
                if (deque.getFirst() == i - k) {
        
                    deque.removeFirst();
                }
                //输出结果
                if (i >= k - 1) {
        
                    res[i - k + 1] = nums[deque.getFirst()];
                }
            }
            return res;
         }
    }

## 2. 无重复字符的最长子串 ##

题目来源于 LeetCode 上第 3 号问题：无重复字符的最长子串。题目难度为 Medium，目前通过率为 29.0% 。

### 题目描述 ###

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

**示例 1:**

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

### 题目解析 ###

建立一个256位大小的整型数组 freg ，用来建立字符和其出现位置之间的映射。

维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

*  （1）如果当前遍历到的字符从未出现过，那么直接扩大右边界；
 *  （2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
 *  （3）重复（1）（2），直到左边索引无法再移动；
 *  （4）维护一个结果res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果。

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 1] 动画描述

### 代码实现 ###

// 滑动窗口
    // 时间复杂度: O(len(s))
    // 空间复杂度: O(len(charset))
    class Solution {
         
    public:
        int lengthOfLongestSubstring(string s) {
        
            int freq[256] = {
        0};
            int l = 0, r = -1; //滑动窗口为s[l...r]
            int res = 0;
            // 整个循环从 l == 0; r == -1 这个空窗口开始
            // 到l == s.size(); r == s.size()-1 这个空窗口截止
            // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
            while(l < s.size()){
        
                if(r + 1 < s.size() && freq[s[r+1]] == 0){
        
                    r++;
                    freq[s[r]]++;
                }else {   //r已经到头 || freq[s[r+1]] == 1
                    freq[s[l]]--;
                    l++;
                }
                res = max(res, r-l+1);
            }
            return res;
        }
    };

## 3. 存在重复元素 II ##

题目来源于 LeetCode 上第 219 号问题：存在重复元素 II。题目难度为 Easy，目前通过率为 33.9% 。

### 题目描述 ###

给定一个整数数组和一个整数 *k*，判断数组中是否存在两个不同的索引 *i* 和 *j*，使得 **nums \[i\] = nums \[j\]**，并且 *i* 和 *j* 的差的绝对值最大为 *k*。

**示例 1:**

输入: nums = [1,2,3,1], k = 3
    输出: true

**示例 2:**

输入: nums = [1,0,1,1], k = 1
    输出: true

**示例 3:**

输入: nums = [1,2,3,1,2,3], k = 2
    输出: false

### 题目解析 ###

使用用滑动窗口与查找表来解决。

*  设置查找表`record`，用来保存每次遍历时插入的元素，`record`的最大长度为`k`
 *  遍历数组`nums`，每次遍历的时候在`record`查找是否存在相同的元素，如果存在则返回`true`，遍历结束
 *  如果此次遍历在`record`未查找到，则将该元素插入到`record`中，而后查看`record`的长度是否为`k + 1`
 *  如果此时`record`的长度是否为`k + 1`，则删减`record`的元素，该元素的值为`nums[i - k]`
 *  如果遍历完整个数组`nums`未查找到则返回`false`

### 动画描述 ###

动画描述

### 代码实现 ###

// 时间复杂度: O(n)
    // 空间复杂度: O(k)
    class Solution {
         
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
        
            if(nums.size() <= 1)  return false;
            if(k <= 0)  return false;
            unordered_set<int> record;
            for(int i = 0 ; i < nums.size() ; i ++){
        
                if(record.find(nums[i]) != record.end()){
        
                    return true;
                }
                record.insert(nums[i]);
                // 保持record中最多有k个元素
                // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
                if(record.size() == k + 1){
        
                    record.erase(nums[i - k]);
                }
            }
            return false;
        }
    };

## 4. 长度最小的子数组 ##

题目来源于 LeetCode 上第 209 号问题：长度最小的子数组。题目难度为 Medium，目前通过率为 37.7% 。

### 题目描述 ###

给定一个含有 **n** 个正整数的数组和一个正整数 **s ，**找出该数组中满足其和 **≥ s** 的长度最小的连续子数组**。**如果不存在符合条件的连续子数组，返回 0。

**示例:**

输入: s = 7, nums = [2,3,1,2,4,3]
    输出: 2
    解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

### 题目解析 ###

定义两个指针 left 和 right ，分别记录子数组的左右的边界位置。

*  （1）让 right 向右移，直到子数组和大于等于给定值或者 right 达到数组末尾；
 *  （2）更新最短距离，将 left 像右移一位, sum 减去移去的值；
 *  （3）重复（1）（2）步骤，直到 right 到达末尾，且 left 到达临界位置

### 动画描述 ###

设置滑动窗口的长度为 0 ，位于数轴的最左端。

##### 1. 滑动窗口右端 R 开始移动，直到区间满足给定的条件，也就是和大于 7 ，此时停止于第三个元素 2，当前的最优长度为 4 #####

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1] 图 1

##### 2. 滑动窗口左端 L 开始移动，缩小滑动窗口的大小，停止于第一个元素 3，此时区间和为 6，使得区间和不满足给定的条件（此时不大于 7） #####

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2] 图片 2

#### 3. 滑动窗口右端 R 继续移动，停止于第四个元素 4，此时和位 10 ，但最优长度仍然为 4 ####

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3] 图片 3

### 代码实现 ###

// 滑动窗口的思路
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    class Solution {
        
        public int minSubArrayLen(int s, int[] nums) {
        
            int l= 0,r = -1;    // nums[l...r]为我们的滑动窗口
            int sum = 0;
            int result = nums.length + 1;
            while (l < nums.length){ // 窗口的左边界在数组范围内,则循环继续
    
                if( r+1 <nums.length && sum < s){
        
                    r++;
                    sum += nums[r];
                }else { // r已经到头 或者 sum >= s
                    sum -= nums[l];
                    l++;
                }
    
                if(sum >= s){
        
                    result = (r-l+1) < result ? (r-l+1) : result ;
                }
            }
            if(result==nums.length+1){
        
                return 0;
            }
            return result;
        }
    }

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[数据结构与算法：三十张图弄懂「图的两种遍历方式」][Link 2]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 3]

[几道和散列（哈希）表有关的面试题][Link 4]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 5]

[几道和「堆栈、队列」有关的面试算法题][Link 6]

[链表算法面试问题？看我就够了！][Link 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20220216/edca927d18ea46d49a5aba3176c7f541.png
[640_wx_fmt_gif]: /images/20220216/74dba9e3441c4155b74127ccf4873fbe.png
[640_wx_fmt_gif 1]: /images/20220216/23e929454f924b2d8a6d224e96a4d395.png
[640_wx_fmt_jpeg 1]: /images/20220216/f9102506ea0a4757b11edf5497c6bd82.png
[640_wx_fmt_jpeg 2]: /images/20220216/42d4a2dd712f4809b31516d60b1d2b2a.png
[640_wx_fmt_jpeg 3]: /images/20220216/551fcb4d659a450fa4bb1d3af045a3e3.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 4]: /images/20220216/a42a352c3a23453cbf910ac8ed81e9b5.png
[640_wx_fmt_png]: /images/20220216/626db3897fc64ddcbb0dea8731db4014.png