day38 滑动窗口

1. 滑动窗口

应用场景： 满足xxx条件（计算结果、出现次数、同时包含）
关键词：最长最短子串无重复等等
1）最长
左右指针在起始点，R 向右依次滑动循环；
如果： 窗内元素满足条件，R向右扩大窗口，并更新最优结果；
如果：窗内元素不满足条件，L向右缩小窗口；
2）最短
左右指针在起始点，R 向右依次滑动循环；
如果： 窗内元素满足条件，L向右缩小窗口，并更新最优结果；
如果：窗内元素不满足条件，R向右扩大窗口；
代码模板：

最长
初始化 left right result bestResult
while(右指针没有到结尾){窗口扩大，加入righjt对应的元素，更新当前的resultwhile(result不满足要求){窗口缩小，移除left对应元素，left右移}更新最优结果 bestResultright++;
}
返回bestResult;最短
初始化 left right result bestResult
while(右指针没有到结尾){窗口扩大，加入righjt对应的元素，更新当前的resultwhile(result满足要求){更新最优结果 bestResult窗口缩小，移除left对应元素，left右移}right++;
}
返回bestResult;

2.例题:

设置左标识跟右标识，还有same（无重复时置0，有重复时置1）

此题设置两个循环，第一个循环遍历整个字符串，第二个循环遍历并判断无重复子串。
当left<right时，进行第二个for循环
令j=left，不能超过右标识right，并将same置0；

int lengthOfLongestSubstring(char * s){int i,j,max=0;int left=0,right=0;int same=0;int len=strlen(s);for(i=0;i<len;i++){if(left<right){same=0;for(j=left;j<right;j++){if(s[j]==s[right]){//若有重复字符，将same置1并跳出循环；same=1;break;}}if(same==1){//若有重复字符将left右移left=j+1;}}max=max<(right-left+1)?(right-left+1):max;right++;//right右移继续判断}return max;
}

int longestOnes(int* nums, int numsSize, int k){//挑出连续最长的1的个数int left = 0, lsum = 0, rsum = 0;int ans = 0;for (int right = 0; right < numsSize; right++) {rsum += 1 - nums[right];while (lsum < rsum - k) {// l + r < k lsum += 1 - nums[left];left++;}ans = fmax(ans, right - left + 1);}return ans;
}