👉无重复字符的最长子串👈
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入:
s = "abcabcbb"输出:
3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
子串和子序列的区别
- 子串：原字符串中必须连续的一段
- 子序列：原字符串中可以不连续的一段
- 注意：无论是子串和子序列，元素的顺序都是原序列中的顺序
思路一
利用两个for循环来遍历字符串s，求出无重复字符的最长子串的长度。具体实现方式：首先第一层for循环内部定义一个辅助的整型数组mark，元素的个数为128（对应ASCII值用128个），并初始化为 0（0 表示当前位置上的字符没有出现过，1 表示当前位置上的字符已经出现过了）。第二层for循环里，需要判断当前位置上的字符是否出现过。如果出现过，就直接退出第二层的for循环，不再往后寻找了；如果没有出现过，就将该位置字符在mark数组中对应的位置上的元素值改为 1，然后再刷新无重复字符的最长子串的长度。两层for循环结束后，返回结果即可。
Plain Text
自动换行
xxxxxxxxxx
1
int myMax(int a, int b)
2
{
3
return a > b ? a : b;
4
}
5
6
int lengthOfLongestSubstring(char * s)
7
{
8
int len = strlen(s);
9
int max = 0;
10
int i = 0;
11
for(i = 0; i < len; i++)
12
{
13
int mark[128] = {0};
14
int j = 0;
15
for(j = i; j < len; j++)
16
{
17
if(mark[s[j] - '\0'])
18
{
19
break;
20
}
21
mark[s[j] - '\0'] = 1;
22
max = myMax(max, j - i + 1);
23
}
24
}
25
return max;
26
}
27
分析：这种解法的时间复杂度为O(N^2)，N为字符串的长度，空间复杂度为O(M)，M为 ASCII 码表中字符的个数。
其实这道题还有更优的解法，大家请看思路二。
思路二
首先，我们必须知道一个事实就是：无重复字符的最长子串肯定是以某个字符结尾的。那么我们只需要求出，分别以0 ~ len - 1（len为字符串的长度）位置上的字符结尾的无重复字符子串的长度，那么这些长度之间最大的长度就是无重复字符的最长子串的长度。
那以i位置上的字符结尾的无重复字符子串的长度怎么求呢？该长度取决于i位置上的字符上一次出现的位置以及以i - 1位置上的字符结尾的无重复字符子串的长度。只要知道了这两个条件，我们就能求出以i位置上的字符结尾的无重复字符子串的长度。那为什么会这样呢？见下图解释。
现在我们需要定义定义几个变量来解决这道题目，last数组记录的是每个字符上一次出现的位置，preMaxLen表示以i-1位置上的字符结尾的无重复字符子串的长度，max记录最长子串的长度。last数组中的元素都初始化为 -1，-1表示字符还没有出现过。因为第一个字符上一次出现的位置就是 0 ，所以last[s[0] - '\0'] = 0。又因为以 0 位置上的字符结尾的无重复字符子串的长度是已知的，长度为1，所以max = 1 preMaxLen = 1，for循环从 1 位置开始。那现在我们来看一下代码。
int myMin(int a, int b) { return a < b ? a : b; } int myMax(int a, int b) { return a > b ? a : b; } int lengthOfLongestSubstring(char * s) { int len = strlen(s); if(len == 0) { return 0; } int last[128] = { 0 }; int i = 0; //初始化每个字符上一次出现的位置为-1 for(i = 0; i < 128; i++) { last[i] = -1; } //dp[0] = 1 以0位置上的字符结尾的子串长度为1 last[s[0] - '\0'] = 0; int max = 1;//max记录最长子串的长度 int preMaxLen = 1;//preMaxLen表示以i-1位置上的字符结尾的无重复字符子串的长度 for(i = 1; i < len; i++) { preMaxLen = myMin(i - last[s[i] - '\0'], preMaxLen + 1); //myMin(i-last[s[i]-'\0'], preMaxLen+1)为以i位置上的字符结尾的无重复字符子串的长度 max = myMax(max, preMaxLen); last[s[i] - '\0'] = i;//记录每个字符上一次出现的位置 } return max; }
分析：这种解法的时间复杂度为O(N)，N为字符串的长度，空间复杂度为O(M)，M为 ASCII 码表中字符的个数。该解法之所以能够优化到O(N)的时间复杂度，是将前面遍历得到的信息利用了起来。这也是动态规划的一种基本思路。
👉总结👈
本篇文章主要讲解了子串和子序列的区别和一道经典的LeetCode题-无重复字符的最长子串。如果大家觉得文章写得不错，大家给个三连支持一下哦！谢谢大家啦！💖💝❣️
