前言
大家好，今天我们来讨论一下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?right-left:minlen;
sum-=nums[left++]; // 左下标需要右移
}
}
return minlen==numsSize+1?0:minlen; // 特例2
}
运行实例：
文章来源：https://www.toymoban.com/news/detail-801818.html
总结
以上就是今天讲解的滑动窗口的全部内容，题目不难，也不难讲。
有些过程看似不必要，不过却可以拓宽我们的思路，拓展我们的视野。如果有什么疑问或者建议都可以在评论区留言，感谢大家对
的支持。文章来源地址https://www.toymoban.com/news/detail-801818.html
到了这里，关于【无重复字符的最长子串--三种方法】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
