目录：

  • 前言
  • 一、题目 –无重复字符的最长子串
    • （一）双层循环
      • 1.题目分析
      • 2.图解
      • 3.示例
    • （二）滑动窗口
      • 1.题目分析
      • 2.图解
      • 3.示例
    • （三）滑动窗口–改进
      • 1.题目分析
      • 2.图解
      • 3.示例
  • 二、题目–长度最小的子数组
    • （一）滑动窗口
      • 1.题目解析
      • 2.图解
      • 3.示例
  • 总结

前言

大家好，今天我们来讨论一下LeetCode上两道数组方面的例题来为大家讲解滑动窗口的使用。
题目不难，方法很多。熊猫希望通过第一道简单的题目来使大家了解到不同的解题方法。

一、题目 –无重复字符的最长子串

题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
点击跳转

（一）双层循环

1.题目分析

题目要求找出不含重复字符的最长子串，那么我的第一想法可能就是暴力求解：
我们需要两层循环，第一层循环遍历字符串、并且记录第二层循环开始的位置。
①创建一个新的数组；
②从第一个字符开始遍历，不重复的字符就将它放到新的数组中，遇到重复的就停止，计算该子串的长度；
③开始下一次循环，直到遍历到字符串结束。
那么下面我们就来实现一下这个操作。

在写力扣题的时候我们一定要判断空指针的情况！！

2.图解

3.示例

 int lengthOfLongestSubstring(char* s) { if (s == NULL) // 判断空指针 return 0; int len = strlen(s); int maxlength = 0; // 记录最长长度 int i = 0; for (i = 0; i < len; i++) // 外层循环遍历字符串 { int curlength = 0; // 记录每一次的长度 char* tmp = (char*)calloc(len, 1); // 用来存放子串 int t = 0; int j = i; // 从i开始遍历 while (s[j] && !strchr(tmp,s[j])) // 要防止子串出现越界情况 { tmp[t++] = s[j++];// 字符不存在就保存 } curlength = t; // 子串的长度 if (maxlength < curlength)// 找最长 { maxlength = curlength; }}free(tmp); return maxlength; }

运行实例：

（二）滑动窗口

1.题目分析

通过上面的示例我们已经解决了问题，但是有一个问题：上面的解法时间复杂度很高：O(n^2)，
通过画图我们可以发现内循环每进行一次都会有数据被重复移动，这个操作消耗了大量的时间，
下面我们通过滑动窗口的方法来进行化简。

2.图解

静态图：

动图：
注：动图表示的是tmp数组中应该存放的数据

滑动窗口

3.示例

示例：

int lengthOfLongestSubstring(char* s) {if (s == NULL)return 0;int len = strlen(s);char* tmp = (char*)calloc(len, 1);int right = 0; // 有效字符串长度int maxlength = 0; // 记录最长长度int i = 0;for (i = 0; i < len; i++){char* p = strchr(tmp, s[i]);tmp[right] = s[i];right++;if (p) // 如果该字符已存在，就跳到该位置{right = right - (p - tmp) - 1; // 更新长度char* eff = (char*)malloc(right);// 跳过中间重复的部分memcpy(eff, p + 1, right); // 先将有无重复的字符串保存memset(tmp, '0', (p - tmp + 1 + right));//清空原字符串memcpy(tmp, eff, right); // 将新字符串重新拷贝回去free(eff);}if (maxlength < right)// 找最长{maxlength = right;}}return maxlength;}

运行实例：
![在这里插入图片描述]直https://接上传(blog.csdnimg.c-/fd4nUsR5cd89ed1e4b4085e4047a09c1b891.png)https:/

（三）滑动窗口–改进

1.题目分析

上面我们通过字符的复制和删除来省略了多次遍历的过程，不过，
我们在删除字符的时候需要将后面全部的字符都往前移，这样也需要浪费一些时间，
那么我们是否可以通过找到最长子串的具体位置，来省去删除字符的过程呢？
答案肯定是可以的，下面就让我们开始实际操作。

2.图解

3.示例

示例：

int lengthOfLongestSubstring(char* s) {if (s == NULL)return 0;int len = strlen(s);char* tmp = (char*)calloc(len, 1);int right = 0; // 当前字符串长度int left = 0; // 控制子串起始位置int maxlength = 0; // 记录最长长度for (int i = 0; i < len; i++){char* p = strchr(tmp + left, s[i]);//这里需要注意的一点是字符必须先判断后复制tmp[right] = s[i];right++;if (p) // 如果该字符已存在，就跳到前面重复字符的下一个位置{left = p - tmp + 1;}int curlength = right - left; // 当前子串长度if (maxlength < curlength)// 找最长{maxlength = curlength;}}free(tmp);return maxlength;}

运行实例：

二、题目–长度最小的子数组

题目描述：给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

点击跳转

（一）滑动窗口

1.题目解析

题目要求找一段连续子数组，并且该子数组的和sum要>=target，那么我们首先就是要遍历数组求和，直到sum>=target，
下面我们直接使用滑动窗口的思想进行破题： 那么我们在这里会遇到哪些特殊情况呢？
特例1.整个数组的和都小于target，不过当窗口的右边界越界的时候我们已经跳出循环了，所以也就不需要再做特殊处理；
特例2.有一个数组元素特别大，我们减去前面的一个元素后，sum依然大于target，这时我们就需要先将sum的值不断减小之后才能继续扩大右边界。

2.图解

滑动窗口2

滑动窗口3

3.示例

代码如下：

int minSubArrayLen(int target, int* nums, int numsSize){int minlen=numsSize+1; // 最短长度int sum=0; // 求和int left=0; // 记录左边界int right = 0;while(right<numsSize) // 右边界改变{sum+=nums[right++]; // 这里需要更新right，否则结果会少一while(sum>=target)// 特例1{minlen = minlen>right-left" />-left:minlen;sum-=nums[left++]; // 左下标需要右移}}return minlen==numsSize+1?0:minlen; // 特例2}

运行实例：

总结

以上就是今天讲解的滑动窗口的全部内容，题目不难，也不难讲。
有些过程看似不必要，不过却可以拓宽我们的思路，拓展我们的视野。如果有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。