数据结构和算法笔记1：滑动窗口

在一些数组或者字符串我们需要遍历子序列，可能要用到两个指针（我们称为起始指针和终止指针）进行双层遍历，内层终止指针满足条件时跳出内层循环，然后起始指针前进，回溯终止指针到起始指针，以此继续进行遍历，然而这样效率比较低，我们可能进行了很多不必要的比较。有没有可能只进行一次遍历呢？滑动窗口提供了一个很好的思路。

在滑动窗口算法中我们要解决以下问题：

窗口内是什么？

窗口就是满足条件的子序列。

如何移动窗口的起始位置？

当前窗口的值满足条件了，窗口的起始指针就要向前移动了（也就是该缩小窗口）。

如何移动窗口的结束位置？

窗口的结束位置就是遍历数组的终止指针，也就是一次遍历（for循环）的索引。把整个数组遍历完，终止指针到了最后一个索引，移动窗口就结束了。

代码模板：

int i = 0, j = 0;//i是终止指针，j是起始指针
for (; i < s..size(); i++)//s是序列，i是一遍遍历的终止指针
{
	//对s[i]的操作
  
  // 窗口满足条件就更新数据，起始指针要移动
  while(窗口满足条件){
  	//记录或更新数据
  	...
  	
  	//起始指针移动一位
  	j++;

	//记录或更新数据
  	...
  }
  //返回结果

练习题：牛客网-牛牛的数组匹配

牛牛刚学会数组不久，他拿到两个数组 a 和 b，询问 b 的哪一段连续子数组之和与数组 a 之和最接近。
如果有多个子数组之和同样接近，输出起始点最靠左的数组。

输入描述：

第一行输入两个正整数 n 和 m ，表示数组 a 和 b 的长度。第二第三行输入 n 个和 m 个正整数，表示数组中 a 和 b 的值。

输出描述：

输出子数组之和最接近 a 的子数组

示例1

输入：
2 6
30 39
15 29 42 1 44 1

输出：
29 42

示例2

输入：
6 1
50 47 24 19 46 47
2

输出：
2

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[n], b[m];
    int sum_a = 0; 
    int sum_b = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        sum_a += a[i];
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> b[i];
    }
    int j = 0;
    int left = 0, right = 0;
    int res = abs(b[0] - sum_a);//初始化b子序列和sum_b和sum_a的差
    for (int i = 0; i < m; i++)
    {
        sum_b += b[i];

        while (sum_b >= sum_a)//找到sum_b中超过sum_a的分界线，sum_b-b[i]<sum_a，sum_b>=sum_a
        {
            
            if (sum_b - b[i] > 0) //sum_b由两个及以上的数相加而成（sum_b >= sum_a）
            {
                if (abs(sum_b - b[i] - sum_a) < abs(sum_b - sum_a))//sum_b-b[i]比sum_b更接近sum_a
                {
                    if (abs(sum_b - b[i] - sum_a) < res)//找到更接近sum_a的和：sum_b - b[i]，更新起始指针和终止指针
                    {
                        right = i - 1;
                        left = j;
                        res = abs(sum_b - b[i] - sum_a);
                    }
                    sum_b -= b[j++];
                }
                else if (abs(sum_b - b[i] - sum_a) > abs(sum_b - sum_a))//sum_b比sum_b-b[i]更接近sum_a
                {
                    if (abs(sum_b - sum_a) < res)//找到更接近sum_a的和：sum_b，更新起始指针和终止指针
                    {
                        right = i;
                        left = j;
                        res = abs(sum_b - sum_a);
                    }
                    sum_b -= b[j++];
                }
            }
            else //sum_b由一个数相加而成（sum_b >= sum_a）
            {
                right = i;
                left = j;
                res = abs(sum_b - sum_a);
                sum_b -= b[j++];
            }
        }
        if ((i == m - 1) && (j == 0))//排除b数组所有数之和都小于a数组之和情况
        {
        	right = i;
            left = j;
        }     
    }
    
    for (int i = left; i <= right; i++)
        cout << b[i] << " ";
}