敢不敢挑战几道「滑动窗口」有关的面试题？

0.何为滑动窗口算法

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

假设有数组 [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 等。

动画描述

代码实现

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

动画描述

代码实现

// 滑动窗口
// 时间复杂度: 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             if(r + 1 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             if(record.find(nums[i]) != record.end()){
                return true;
            }
            record.insert(nums[i]);
            // 保持record中最多有k个元素
            // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
            if(record.size() == k + 1