滑动窗口算法归纳_滑动算法

1：滑动窗口的概念

      滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。顾名思义，就像一个滑动的窗口，套在一个序列中，左右的滑动，窗口内就是一个内容集。

2：分类：

      窗口有两类，一种是固定大小类的窗口（固定窗口），一类是大小动态变化的窗口（动态窗口）。

3、滑动窗口算法思路

滑动窗口的应用场景有几个特点：

1. 需要输出或比较的结果在原数据结构中是连续排列的；

2. 每次窗口滑动时，只需观察窗口两端元素的变化，无论窗口多长，每次只操作两个头尾元素，当用到的窗口比较长时，可以显著减少操作次数；

3. 窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果时往往要用到窗口中所有元素。

4：该问题本身可以通过暴力或dp求解的；

滑动算法核心模版总结：

1：设置i遍历序列（从头到尾）

2：设置j为新序列开始的头部标记；

3：设置index,记录目标值（长度，和等），根据条件更新

void hd(....)
{
    for(int i=0;i<n;i++)
  {
      for(循环条件)/while(循环条件)
          寻找某一段序列，直到找到符合中断条件的点
      j=；//更新头部，开始新的序列
      index=;//根据题中条件同步更新目标值
  }
  index=;//最后更新，防止上一次更新后一直到尾部都没有中断的情况而出现的遗漏
}

例题：

例题1——固定大小类（一般是求和/积类）：

蓝桥杯算法提高VIP-和最大子序列 - C语言网

#include<stdio.h>
int main()
{
	int n,max;
	int a[100005]={0};
	int sum[10005]={0};
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	max=sum[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		int temp=sum[i-1]+a[i];
		if(temp<sum[i-1])
		{
			sum[i]=0;
		}
		else
		{
			sum[i]=temp;
		}
		if(max<sum[i])
		{
			max=sum[i];
		}
	}
	printf("%d\n",max);
	return 0;
}

例题2——动态型（一般是求长度）：

力扣https://leetcode-cn.com/problems/minimum-size-subarray-sum/

#include<stdio.h>
int main()
{
	int n,s,sum=0,end=0;
	int minlen;
	scanf("%d%d",&n,&s);
	int a[n]={0};
	minlen=n;
	for(int i=0;i<n;i++)//录入数组 
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++) //从头开始找 
	{
		while(sum<s)//找到一个符合条件的序列  
		{
			sum+=a[end];
			end++;
		} 
		if(sum>=s)
		{
			if(minlen>(end-i))
			{
				minlen=end-i;
			} 
		}
		sum-=a[i];//头部向右移动 ，开始下一轮 
	}
	printf("%d\n",minlen);
	return 0; 
}

例题3——动态类型：

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

示例 1:

输入: "abcabcbb"

输出: 3

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

#include<stdio.h>
#include<string.h>
int hd(char a[])
{
	    int i = 0, j = 0;
	    int maxlen = 0;//最大长度 
	    int curlen = 0;//当前长度 
	    int len = strlen(a);//获取字符串长度 
	    if (len == 0)
	        return 0;
	    for (; j < len && len - i > maxlen; j++) {
	        curlen++;
	        for (int k = i; k <= j; k++) 
			{
	            if (a[k] == a[j + 1]) //对比已有的字符串中，是否有与即将出现的下一个字符相同的字符 
				{
	                if (curlen > maxlen)//如果有，则更新当前长度 
	                    maxlen = curlen;
	                i = k + 1;//从出现重复地方开始舍弃前面的字符串，开始新的序列 
	                curlen = j - i + 1;//跟新当前的长度 
	                break;
	            }
	        }
	    }
	return maxlen>curlen?maxlen:curlen;	//跟新最大长度 
}
int main()
{
	char a[10000]={0};
	scanf("%s",a);
	printf("%d\n",hd(a));
}

//整合其他大佬的资料结合自己的理解编写，有错误之处欢迎指正。