滑动窗口详解

算法简介：

滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。

可以想象成队列，一端在push元素，另一端在pop元素，如下所示：

假设有数组[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、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
• 2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
• 3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。
• 4、重复第 2 和第 3 步，直到 right 到达序列的尽头。

思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

 算法模板：

1、单层循环：

def template():
    # 初始化滑动窗口两端
    left = right = 0
    
    # 序列及序列长度
    seq, seq_len = xx, xx

    # 滑动窗口序列
    slide_win = []

    # 结果值
    rst = xx

    while right < seq_len:
        slide_win.append(seq[right])
        # 还没找到一个可行解
        if not avaliable(slide_win):
            # 扩大窗口
            right += 1
        else:
            # 找到一个可行解，更新结果值
            rst = update()
            # 缩小窗口
            left += 1


 

2、双层循环：

def template():
    # 初始化滑动窗口两端
    left = right = 0
    
    # 序列及序列长度
    seq, seq_len = xx, xx

    # 滑动窗口序列
    slide_win = []

    # 结果值
    rst = xx

    while right < seq_len:
        slide_win.append(seq[right])
        # 还没找到一个可行解
        if not avaliable(slide_win):
            # 扩大窗口
            right += 1
            continue

        # 循环更新可行解
        while avaliable(slide_win):
            # 找到一个可行解，更新结果值
            rst = update()
            # 缩小窗口
            left += 1


 

算法实例：

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

1、请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

相信看懂了上面的算法介绍，下面的代码很容易理解

#include<algorithm>
#include <deque>
class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		//使用双端队列，不能使用hash，因为这是一个最长子串，保证窗口里面的元素保持原来的顺序
		deque<char> need;
		size_t max_num = 0;
		int index = 0;
		while (index < s.size())
		{
			if (!judge(need, s[index]))
			{
				need.push_back(s[index]);
				index++;
				continue;
			}
			else
			{
				//更新结果
				max_num = max(max_num, need.size());
				need.pop_front();
			}
		}
		return max_num = max(max_num, need.size());
	}
	bool judge(deque<char>& tmp, char str)
	{
		for (auto &e : tmp)
		{
			if (e == str)
			{
				return true;
			}
		}
		return false;
	}
};

python版本 

from collections import deque


class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        index = 0
        
        # 因为这个滑动窗口需要从一端进，一端出，因此考虑采用队列
        slide_win = deque()

        # 因为在滑动过程中需要不断的从窗口中增减元素，因此需要一个变量来保持最大窗口长度
        max_len = 1

        while index < len(s):
            # 一个小的优化点：还没有遍历的元素长度加上当前的窗口长度已经小于最大窗口长度，则直接返回结果
            if len(slide_win) + (len(s) - index) <= max_len:
                return max_len

            # 如果当前元素没有在滑动窗口中，则加入，并且窗口扩大
            if s[index] not in slide_win:
                slide_win.append(s[index])
                index += 1
            else:
                # 如果当前元素已经在窗口中有值，则更新最大窗口长度
                max_len = max(max_len, len(slide_win))
                # 窗口缩小，对端不变
                slide_win.popleft()

        return max(max_len, len(slide_win))
 

 2、绝对差不超过限制的最长连续子数组

https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        if (nums.size() == 0)
			return 0;
		int len = nums.size();
		int left = 0;
		int right = 0;
		int max_size = 0;
		vector<pair<int, int>> max_heap;
		make_heap(max_heap.begin(), max_heap.end(), less<pair<int, int>>());
		
		vector<pair<int, int>> min_heap;
		make_heap(min_heap.begin(), min_heap.end(), greater<pair<int, int>>());
		while (right < len)
		{
			max_heap.push_back(pair<int,int> (nums[right], right));
			push_heap(max_heap.begin(), max_heap.end(), less<pair<int, int>>());
			
			min_heap.push_back(pair<int, int>(nums[right], right));
			push_heap(min_heap.begin(), min_heap.end(), greater<pair<int, int>>());

			int diff = max_heap[0].first - min_heap[0].first;

			if (diff <= limit)
			{
				right++;
				continue;
			}
			//最大差值超过设定，更新最大窗口的值
			max_size = max(max_size, right-left);//不能使用堆的size，因为窗口中的不是最优解
			//保证滑动窗口中的最大差值在要求的范围内
			while (max_heap[0].first-min_heap[0].first>limit)
			{
				//去掉大顶堆中所有的在窗口之外的最大元素
				while (max_heap[0].second<=left)
				{
					pop_heap(max_heap.begin(), max_heap.end(), less<pair<int, int>>());
					max_heap.pop_back();
				}
				while (min_heap[0].second<=left)
				{
					pop_heap(min_heap.begin(), min_heap.end(), greater<pair<int, int>>());
					min_heap.pop_back();
				}
				left++;
			}
		}
		return max(max_size, right - left);
    }
};

 

    从上面两个例子来看，所体现的算法思想不变，都是找到符合条件的窗口，然后去求当前的最优解，实现手段不同，第一个比较简单，直接利用deque的特性很容易完成。第二个要求复杂了一点， 求相互的差值不超过设定，其实说到相互的差值不超过设定，不就是最大的差值不超过设定嘛，（有时遇到棘手的问题，看看换一种思考能不能更简单的实现），想到了大小堆，问题就迎刃而解了。

     在优化窗口的时候，一般就是左指针的天下了，通过左指针作为参照或者直接将不满足左指针条件的窗口中的值删除。知名的算法思想相同，致命的是细节的把控。

3、子数组查找

链接：https://www.nowcoder.com/questionTerminal/4406e29ed847446e9745d75f43fad3fe
来源：牛客网

给定长度为N的整数数组，以及M个互不相同的整数，请找出包含这M个整数的最短子数组。

例如：给定数组[4 2 1 3]，包含数字集{2, 3}的最短子数组是[2 1 3]，包含数字集{1, 3}的最短子数组是[1 3]。

 

下面的代码直接将代码复杂度降到O(1)级别，利用hash表优化子窗口求解过程，不过思想理解起来稍显复杂，不理解的还是乖乖使用deque吧，在时间复杂度要求不是很严的情况下。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int func(vector<int>& v, vector<int>& u)
{
	unordered_map<int, int> need, window;
	for (int i : u)
		need[i]++;
	int l = 0, r = 0;
	int valid = 0;
	int ans = v.size() + 1;
	while (r < v.size())
	{
		int t = v[r];
		r++;
		if (need.count(t))
		{
			window[t]++;
			if (need[t] == window[t])
				valid++;
		}
		//找到符合条件的区间，接下来要寻求最优解
		while (valid == need.size())
		{
			ans = min(ans, r - l);
			int t = v[l];
			l++;
			if (need.count(t))//是因为并不确定他是不是need的最左边的，用deque就很简单了
			{
				if (need[t] == window[t])
					valid--;
				window[t]--;
			}
		}
	}
	return ans == v.size() + 1 ? 0 : ans;
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int M, N, t;
		cin >> N;
		vector<int> v;
		while (N--)
		{
			cin >> t;
			v.push_back(t);
		}
		cin >> M;
		vector<int> u;
		while (M--)
		{
			cin >> t;
			u.push_back(t);
		}

		cout << func(v, u) << endl;
	}
}

给定一个序列，求序列中连续的数字之和等于目标值的子序列长度最短的两个？

例如  40 20 20 40 40 80       子序列和等于80  的序列有 40 20 20 、20 20 40 、40 40 、 80

//
// Created by didi on 2020-08-18.
//

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
using namespace std;

class Solation
{
public:

    int get_sum()
    {
        return sum;
    }
    int get_size()
    {
        return de.size();
    }
    bool Pop()
    {
        int tmp=de.front();
        de.pop_front();
        sum -= tmp;
        return true;
    }
    bool Push(int tmp)
    {
        de.push_back(tmp);
        sum += tmp;
        return true;
    }
    int sum=0;
    deque<int> de;
};

int main()
{

    int num=0;
    cin>>num;
    int len=num;
    vector<int> ret;
    while(num)
    {
        --num;
        int tmp=0;
        cin>>tmp;
        ret.push_back(tmp);
    }
    int task=0;
    cin>>task;
    //暴搜版
//    set<int> me;
//    for(int i=0;i<len;++i)
//    {
//        int mem = ret[i];
//        int l=1;
//        if(mem==task)
//        {
//            me.insert(l);
//            continue;
//        }
//        for(int j=i+1;j<len;++j)
//        {
//
//            mem+=ret[j];
//            l++;
//            if(mem==task)
//            {
//                me.insert(l);
//                break;
//            }
//        }
//    }
//    for(auto &e:me)
//    {
//        cout<<e<<" ";
//    }

    //滑动窗口版
    int right = 0;
    int left=0;
    Solation test;
    set<int> me;
    while(right<=len)
    {
        if(test.get_sum()<task)
        {
            test.Push(ret[right]);
            right++;
        }
        if(test.get_sum()==task)
        {
            me.insert(test.get_size());
            test.Pop();
            //right++;
        }
        while(test.get_sum()>task)
        {
            test.Pop();
        }
    }
    for(auto &e:me)
    {
        cout<<e<<" ";
    }


    return 0;
}