算法题滑动窗口_LeetCode刷题手册

滑动窗口三步走：

第一步确定尾指针++的条件，往右扩张；第二步确定头指针++的条件，往右收缩，第三步更新所求目标值（一般都是极值）

滑动窗口伪代码：

start = 0 end = 0 //初始化 while（扩张条件） { while（收缩条件） { FindTarget（）//收缩时一般求极小值 start++//收缩，有可能是++，也有可能是跳跃式移动 } FindTarget（）//扩张时一般求极大值 end++//扩张，一般都是++ } if（一次都没进入过收缩条件） { 特殊处理一下 }

目前来看，滑动窗口主要有两种题型，一种是找最长/最短子数组，这种使用上述的三步走策略。另一种是固定长度的窗口内的极值，此时需要借助单调队列

题目一：209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路：

for（遍历整个字符串） { for（和值大于target） { 计算一次最短长度 头指针右移收缩 } 尾指针右移扩张 } 没收缩过需要特殊处理

代码：

int minSubArrayLen(int target, int* nums, int numsSize) { int start = 0, end = 0; int sum = 0, minlen = INT_MAX, tmp = 0; while (end < numsSize) { sum += nums[end]; while (sum >= target) { tmp = end - start + 1; if (minlen > tmp) { minlen = tmp; } sum -= nums[start]; start++; } end++; } return minlen == INT_MAX ? 0 : minlen; }

题目二：3. 无重复字符的最长子串

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

示例 1:

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

思路：

for（遍历字符串） { for（出现了重复字符） { 头指针右移內缩，右移到重复字符后面一位的地方，保证新的串口内没有重复字符 } 尾指针右移扩张 每次扩张计算一次最大距离 }

代码：

int lengthOfLongestSubstring(char * s){ int start = 0, end = 0, len = 0, output = 0; int chs[128] = {0}; if (0 == strlen(s) || NULL == s) { return 0; } for (end = 0; s[end] != '\0'; end++) { //难点1：chs[s[end]]内保存的是目标字符最近一次出现的位置，方便头指针右移找位置 if (chs[s[end]] > start) { //难点1相关处理 start = chs[s[end]]; //目标是求最长距离，它更可能出现在扩张的过程中 //本题收缩时计算和扩张时计算完全重复，则可以省略 //len = end - start + 1; //output = output < len ? len : output; } //难点1相关处理 chs[s[end]] = end + 1; len = end - start + 1; output = output < len ? len : output; } return output; }

题目三：76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

思路：

for（遍历整个字符串） { for（s中出现了t中的所有元素） { 计算最小覆盖长度 头指针右移收缩 } 尾指针右移扩张 }

代码：

char * minWindow(char * s, char * t){ int start = 0, end = 0; int slen = strlen(s); int tlen = strlen(t); int chst[128] = {0}; int minlen = INT_MAX, minlenindex; int tmplen; //统计t中所有字符出现的次数 for (end = 0; end < tlen; end++) { chst[t[end]]++; } end = 0; while (end < slen) { if (chst[s[end]] > 0) { //此时tlen的大小代表s已经出现了(strlen(t) - tlen)个t中的元素 tlen--; } //chst[i]为正，代表s中还需出现chst[i]次字符i，才会使s与t中出现i的次数相同 //chst[i]为负，代表字符i只在s中出现 chst[s[end]]--; //难点：tlen==0 时代表s中已经出现了t中所有的元素（包括重复的元素） //同时，也作为头指针收缩的条件 while (0 == tlen) { //更新最小覆盖距离 tmplen = end - start + 1; if (minlen > tmplen) { minlen = tmplen; minlenindex = start; } chst[s[start]]++; if (chst[s[start]] > 0) { //代表收缩后的窗口不满足条件了，需要扩张 tlen++; } start++; } end++; } //收缩过至少一次 if(minlen != INT_MAX) { char* t = (char*)malloc(sizeof(char)*(minlen+1)); *t = '\0'; strncat(t, s+minlenindex, minlen); return t; } //一次都没收缩过 return ""; }

题目四：239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

思路：滑动窗口找极值，采用单调队列思想

//由于窗口长度被固定了，所以没有动态的收缩扩张过程 for（维护滑动窗口的移动，直到遍历结束） { 维护一个单调队列，保证队头指针指向的元素一定是窗口内的最大值，且整个队列保持从左到右单调递减 对于每一次窗口向前移动，对应删除一个旧元素,增加一个新的元素(必须先判断出队，再判断入队) 每移动一次就把队头元素输出一次 } //难点1：判断出队的元素是不是队头元素 //难点2：队头元素出队后如何使队头指针指向新的队头 //难点3：入队的元素找到位置后直接覆盖旧元素，可以省略数组插入新元素的过程

代码：

typedef struct Queue { int head; int tail; int * data; }MyQueue; int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) { int* output = malloc(sizeof(int) * numsSize); MyQueue q; int i, j = 0; q.head = 0; q.tail = 0; q.data = malloc(sizeof(int) * numsSize); *returnSize = 0; for (i = 0; i < numsSize; i++) { //data内存的是数组下标，而非数组元素，目的是方便队头元素出队后，队头指针head容易找到下一个队头 //data[head]处于窗口外了（被出队了），更新队头指针 if (q.data[q.head] <= i - k && q.head < q.tail) { q.head++; // 出队后的下一个元素就是最大的 } //给新入队的元素找在单调队列中的位置（在队尾指针指向的位置直接覆盖） for (j = q.tail; j > q.head; j--) { if (nums[q.data[j - 1]] < nums[i]) { q.tail--; } //这里用for循环会超时的原因 //1. 多给j进行了++操作 //2. 如果不加beark，每次会进行多余的循环 else { break; } } #if 0 if (q.tail > q.head) { while (q.tail > q.head && nums[q.data[q.tail - 1]] < nums[i]) { q.tail--; } } #endif q.data[q.tail++] = i; //前k个元素不输出（等待窗口成型） if (i >= k - 1) { output[(*returnSize)++] = nums[q.data[q.head]]; } } return output; }