【算法集训】基础算法：滑动窗口

定义一个快慢指针，用于截取数组中某一段信息。同时可以改变快慢指针的值来获取结果，这个过程比较像滑动。

1493. 删掉一个元素以后全为 1 的最长子数组

• 定义快慢指针
• 快指针先走，如果到了第二个0上的时候。前面1的个数就是fast - slow - 1，但是为了后面的继续计算，需要将slow指针+1即可。

// 滑动窗口
int longestSubarray(int* nums, int numsSize) {// 定义快慢指针int slow = 0;int fast = -1;// 记录0的个数int zero = 0;// 最大长度int maxlen = 1;// 快指针走while(fast < numsSize - 1) {fast++;zero += !nums[fast];while(zero > 1) {zero -= !nums[slow];slow++;}if(fast - slow + 1 > maxlen) {maxlen = fast - slow + 1;}}return maxlen - 1;
}

1004. 最大连续1的个数 III

和上一题一样的，只不过将替换0的值增加为了k个。

int longestOnes(int* nums, int numsSize, int k) {// 定义快慢指针int slow = 0;int fast = -1;int zero = 0;  //记录0的个数int maxlen = 0; //最终的返回的最大长度// 快指针先走while(fast < numsSize - 1) {fast ++;zero += !nums[fast];while( zero > k) {zero -= !nums[slow];slow++;}if(maxlen < fast - slow + 1) {maxlen = fast - slow + 1;}}return maxlen;
}

2730. 找到最长的半重复子字符串

int longestSemiRepetitiveSubstring(char * s){int slow = 0;int fast = -1;int same = 0;int maxlen = 0;int len = strlen(s);// 快指针while(fast < len - 1) {fast++;// 如果快大于慢的话就可以看相邻的相等否了?if(fast - slow > 0) {// 如果相等则同样记录+1if(s[fast] == s[fast - 1]) {same++;}// 当大于1的时候就需要移动慢指针了while( same > 1 ) {if(s[slow] == s[slow + 1]) {--same;}slow ++;}}if(fast - slow + 1 > maxlen) {maxlen = fast - slow + 1;}}return maxlen;
}