【数据结构与算法】无重复字符的最长子串

🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

目录

👉无重复字符的最长子串👈

给定一个字符串 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

循环结束后，返回结果即可。

intmyMax(int a,int b){return a > b ? a : b;}intlengthOfLongestSubstring(char* s){int len =strlen(s);int max =0;int i =0;for(i =0; i < len; i++){int mark[128]={0};int j =0;for(j = i; j < len; j++){if(mark[s[j]-'\0']){break;}
            mark[s[j]-'\0']=1;
            max =myMax(max, j - i +1);}}return max;}

分析：这种解法的时间复杂度为

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 位置开始。那现在我们来看一下代码。

intmyMin(int a,int b){return a < b ? a : b;}intmyMax(int a,int b){return a > b ? a : b;}intlengthOfLongestSubstring(char* s){int len =strlen(s);if(len ==0){return0;}int last[128]={0};int i =0;//初始化每个字符上一次出现的位置为-1for(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题-无重复字符的最长子串。如果大家觉得文章写得不错，大家给个三连支持一下哦！谢谢大家啦！💖💝❣️