1.滑动窗口的思想:
它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。假设有数组 [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]
一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动,能够极大地提高算法地效率
2.滑动窗口的几个例题应用
1。
思考:
滑动窗口算法可以解决字符串的子串中的几类应用问题
主要思想是:left与right同时从0开始变化,哈希表所记录的dict如果出现不止一次,那么就把左边界重新赋值到新出现的位置,右边界不管咋样都向后一个一个的移动,每次都记录下max,max为右减左再加一,因为从0开始。
图解:
源代码:
#include
#include
int lengthOfLongestSubstring(char * s){
if (s == NULL) return 0;
int max = 0; //记录最长的长度max
int left = 0, right = 0; //滑动窗口的左边界和右边界
int dict[256] = {0}; //和前面的排序一样,搞个类似于哈希表的东西,通过数组记录其出现的相应次数;
int index;
for (; s[right] != '\0' ; right++){
index = s[right]; //得到对应字符的下标
if(dict[index] > left)
left = dict[index];
dict[index] = right+1; //注意:到只有一个字符时长度为1,所以这里右边界要加1
if (max < right-left+1)
max = right-left+1; //更新最大值
}
return max;
}
main(){
char a[99];
gets(a);
int n;
n = lengthOfLongestSubstring(a);
printf("%d",n);
}
思考:
同样使用滑动窗口的办法解决,每次循环都求和,同时右边界移动,当和大于目标值时,进入最小值的判断,如果是第一次进入,则让最小值为此时右边界减0,同时sum把左边界的值减去,左边界移动一个,如果不是第一次进入最小值的判断,那么最小值就是右减左边界(此时左边界已经移动)如果不大于目标值则继续原始循环,直到数组的头。
int minSubArrayLen(int s, int* nums, int numsSize){
int left = 0;
int right = 0;
int min = 0;
int sum = 0;
while (right < numsSize){
sum += nums[right];
right++;
while (sum >= s){
if (min == 0){
min = right - left;
}
else{
if(min > right - left)
min = right - left;
}
sum -= nums[left];
left++;
}
}
return min;
}