漫画 | 字节一面：求无重复子串的最长子串

Myth丶恋晨 2022-09-11 05:18 92阅读 0赞

大家好，我是土哥。

作为一名大数据算法工程师，需要有一些算法功底，但是学习算法又非常枯燥，冰冷的 `文字+代码` 往往使大部分读者在学习算法的道路上半途而废。

今天呢，土哥就用 `漫画+动图` 的风格让我的读者轻松、愉快的学习算法，毕竟

![82e57ddcbc81a7105bdd5e5e3ee7f9d2.gif][]

## 故事 ##

今天，小笨猪 **阿土** 收到了字节跳动的一面邀请邮件，约定3天后面试。

这可把 **阿土** 高兴坏了，但是 **阿土**的算法水平比较差，他听说字节跳动每轮面试必考算法，所以心情很忐忑。

这个时候，他的好朋友小美猪 **阿梅** 来找她玩耍，看到小笨猪闷闷不乐，于是问起了缘由，当得知字节跳动每轮都考算法的时候，阿梅说，不要担心，**我们现在就开始刷代码**，正好我今天刚做了一道题，可以考考你。

![f6dd5a2ab3708b18f25b7c7715c7f0f8.png][]

题目描述：
    
    给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    
    示例：
    输入: s = "abcabcbb"
    输出: 3 
    
    输入: s = "bbbbb"
    输出: 1

阿土看了看题目，这个？想了好几分钟，没想出答案。

![2f98d6c3adf422c14d7c70c9b47f5733.png][]

## 题目解析 ##

阿梅看到小笨猪一直没有想出来，于是开始给小笨猪讲解：

### 1、题目思路 ###

这道题主要用到思路是：`滑动窗口`

**什么是滑动窗口？**

其实就是一个队列,比如例题中的 `pwwkew`，进入这个队列（窗口）为 `pw` 满足题目要求，当再进入`w`，队列变成了 `pww`，这时候不满足要求。所以，我们要移动这个队列！

**如何移动？**

我们只要从队列的左边开始将元素移出，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)

### 2、步骤 ###

1.  可以定义一个`map`数据结构存储`（k,v）`,其中`key`为字符，`value`为字符的下标;
2.  我们定义不重复子串的开始位置为`start`,结束位置为`end`. `start` 刚开始不动，`end`向后移动;
3.  当`end`遇到重复字符时，将`start`放在上一个重复字符位置的后一位，同时记录最长的长度`max`;
4.  通过`hashmap`的`key`来判断重复字符，用`value`来记录该字符的下一个不重复的位置。

刚开始，`start` 和 `end` 都处于下标`0`， `max`初始定义为`0`，`hashmap`中没有存放`key` 和 `value`。  
![ad443cb9e511c573afbda2d267ea24f0.png][]

通过`for`循环，从`end`为`0` 开始遍历，判断第`1`个字符`p`，`hashmap`中没有包含`p`,这时将`p`作为`key`存入`map`,下标`0`存入`value`中。  
`max =Math.max(max,end-start +1) =1`，

继续执行，`end = end+1 = 1`如下图：

![de92c957e9580c4bdd6e45bb5e759b2a.png][]

判断第`2`个字符`w`,`hashmap`中没有包含`w`,这时将`w`作为`key`存入`map`,下标`1`存入`value`中。

`max =Math.max(max,end-start +1) =2.`

继续执行, `end = 1+1 = 2`。如下图：  
![e05df65f5c6f9399a7ad50fac6b204c8.png][]

判断第3个字符```w``,hashmap```中包含`w`,这时计算`start`，将`start`放在上一个重复字符位置的后一位，即上一个`w`下标为`1`的后一位，所以  
`start = Math.max(start,map.get(ch)+1)=2。`

然后在`map`中更新`w`下标为`2`，重新计算`max = Math.max(max,end-start +1) =2`, 继续执行，`end = 2+1 = 3`。如下图：

![c0c5b80db6c94c7067b68890ab37fc86.png][]  
判断第`4`个字符`k`,`hashmap`中没有包含`k`,这时将`k`作为`key`存入`map`,下标`3`存入`value`中。`max =Math.max(max,end-start +1) =2`,继续执行，`end = 3+1 = 4`。 如下图：

![065fdf9337adf1cbe8b689a4e9516423.png][]

判断第`5`个字符`e`,`hashmap`中没有包含`e`,这时将作为`key`存入`map`,下标`4`存入`value`中。`max =Math.max(max,end-start +1) =3`, 继续执行，`end = 4+1 = 4`。 如下图：  
![52026c8b012010d243947d2a26f4fa0d.png][]

判断第`6`个字符`w`,`hashmap`中包含`w`,这时计算`start`，将`start`放在上一个重复字符位置的后一位，即上一个`w`下标为`2`的后一位，所以`start = Math.max(start,map.get(ch)+1)=3`。

然后在`map`中更新`w`下标为`5`，重新计算`max = Math.max(max,end-start +1) =3`, 继续执行，`end = 5+1 = 6`。如下图：  
![6de2065d61904867a43c586514c5a45c.png][]

判断`end=6`时，超出字符串范围，程序结束，所以最终字符的长度为`3`。

### 3、动画如下： ###

![185cf89fcb96f73162e8044ef5967a0d.gif][]

![0c208f6fd68e5defedc7c2a0828e0090.png][]

![6c5461841c3e1282e8565e9fcf0cce19.png][]

## 代码实现 ##

### java实现 ###

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
    // (1) 先创建map数据结构存储（k,v）,其中key为字符，value为字符的下标.
         HashMap<Character,Integer> map = new HashMap<>();  
            //(2)定义不重复子串的开始位置为start,结束位置为end. start 刚开始不动，end向后移动 
            int max =  0 , start = 0;
            //(3) 遍历字符串
            for(int end = 0 ; end < s.length() ; end++){ 
                // (4)取出每个字符
                char ch = s.charAt(end);
                // (5)判断字符，hashmap中没有是否包含该字符
                if (map.containsKey(ch)){ 
                // (6)包含字符，将start放在上一个重复字符位置的后一位。
                    start = Math.max(start,map.get(ch)+1);
                }
                // (6)计算max长度
                max = Math.max(max,end -start+1);
                //(7)将字符作为key存入map,下标存入value中
                map.put(ch,end);
    
            }
            // (8)程序执行结束，返回无重复子串最大长度。
            return max;
        }
    }

### c++实现 ###

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.size() == 0) return 0;
            unordered_set<char> lookup;
            int maxStr = 0;
            int left = 0;
            for(int i = 0; i < s.size(); i++){
                while (lookup.find(s[i]) != lookup.end()){
                    lookup.erase(s[left]);
                    left ++;
                }
                maxStr = max(maxStr,i-left+1);
                lookup.insert(s[i]);
        }
            return maxStr;
            
        }
    };

### python3实现 ###

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            if not s:return 0
            left = 0
            lookup = set()
            n = len(s)
            max_len = 0
            cur_len = 0
            for i in range(n):
                cur_len += 1
                while s[i] in lookup:
                    lookup.remove(s[left])
                    left += 1
                    cur_len -= 1
                if cur_len > max_len:max_len = cur_len
                lookup.add(s[i])
            return max_len

![4ac90b0732f00ecad4f856dd334ae8b8.png][]

土哥的代码均已经通过Leetcode在线测评，保证代码是没有问题。原创不易，各位觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！谢谢大家！

最近整理了一份计算机类的书籍，包含python、java、大数据、人工智能、算法等，种类特别齐全。  
获取方式：关注公众号：**3分钟秒懂大数据**，回复：**福利**，就可以获得这份超级大礼！

![33ddb3dcb1ea1198f9fc20e464b651c8.png][]

[82e57ddcbc81a7105bdd5e5e3ee7f9d2.gif]: /images/20220828/ccab6c0c7126406fa78bee1b1728986f.png
[f6dd5a2ab3708b18f25b7c7715c7f0f8.png]: /images/20220828/c44b6f779c104299be6f94a628fb1bee.png
[2f98d6c3adf422c14d7c70c9b47f5733.png]: /images/20220828/6ac6d967b20b45e98d85ff553d7b1a1a.png
[ad443cb9e511c573afbda2d267ea24f0.png]: /images/20220828/9a9871578c5941e1b696f3c3385496fb.png
[de92c957e9580c4bdd6e45bb5e759b2a.png]: /images/20220828/83a3945cd3194b88a47fb9b96cf1c7a1.png
[e05df65f5c6f9399a7ad50fac6b204c8.png]: /images/20220828/a5029b5f26ec41eaabbd6732b48172d7.png
[c0c5b80db6c94c7067b68890ab37fc86.png]: /images/20220828/b1540e27c3c94a25961620d3780d0753.png
[065fdf9337adf1cbe8b689a4e9516423.png]: /images/20220828/78eaa7d8ed28472cb28b9c554b78b52c.png
[52026c8b012010d243947d2a26f4fa0d.png]: /images/20220828/c144e1fac5db4e9893ef3d3e491ddd50.png
[6de2065d61904867a43c586514c5a45c.png]: /images/20220828/eea3b0ad9eed4d01888448878d7af249.png
[185cf89fcb96f73162e8044ef5967a0d.gif]: /images/20220828/4f402e332ef9489a9b8f6b2684b2119c.png
[0c208f6fd68e5defedc7c2a0828e0090.png]: /images/20220828/d8f5f469710c4aac81cde16a05d7f594.png
[6c5461841c3e1282e8565e9fcf0cce19.png]: /images/20220828/194d626db44d429bb6755799ec5988bb.png
[4ac90b0732f00ecad4f856dd334ae8b8.png]: /images/20220828/56897db2a8394f9381bb644640489bbc.png
[33ddb3dcb1ea1198f9fc20e464b651c8.png]: /images/20220828/50244a7882e14581ab3aaa963039729a.png