【无重复字符的最长子串--三种方法】

前言

大家好，今天我们来讨论一下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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

运行实例：

---

（二）滑动窗口

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

运行实例：
![在这里插入图片描述]直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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

运行实例：

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

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

点击跳转

（一）滑动窗口

1.题目解析

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

2.图解

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行实例：

---

总结

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