漫畫 | 位元組一面：求無重復子串的最長子串

大家好，我是土哥，

作為一名大資料演算法工程師，需要有一些演算法功底，但是學習演算法又非常枯燥，冰冷的 文字+代碼 往往使大部分讀者在學習演算法的道路上半途而廢，

今天呢，土哥就用 漫畫+動圖 的風格讓我的讀者輕松、愉快的學習演算法，畢竟

故事

今天，小笨豬 阿土 收到了位元組跳動的一面邀請郵件，約定3天后面試，

這可把 阿土 高興壞了，但是 阿土的演算法水平比較差，他聽說位元組跳動每輪面試必考演算法，所以心情很忐忑，

這個時候，他的好朋友小美豬 阿梅 來找她玩耍，看到小笨豬悶悶不樂，于是問起了緣由，當得知位元組跳動每輪都考演算法的時候，阿梅說，不要擔心，我們現在就開始刷代碼，正好我今天剛做了一道題，可以考考你，

題目描述：

給定一個字串 s ，請你找出其中不含有重復字符的 最長子串 的長度，

示例：
輸入: s = "abcabcbb"
輸出: 3 

輸入: s = "bbbbb"
輸出: 1

阿土看了看題目，這個？想了好幾分鐘，沒想出答案，

題目決議

阿梅看到小笨豬一直沒有想出來，于是開始給小笨豬講解：

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，

通過for回圈，從end為0 開始遍歷，判斷第1個字符p，hashmap中沒有包含p,這時將p作為key存入map,下標0存入value中，
max =Math.max(max,end-start +1) =1，

繼續執行，end = end+1 = 1如下圖：

判斷第2個字符w,hashmap中沒有包含w,這時將w作為key存入map,下標1存入value中，

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

繼續執行, end = 1+1 = 2，如下圖：

判斷第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，如下圖：

判斷第4個字符k,hashmap中沒有包含k,這時將k作為key存入map,下標3存入value中，max =Math.max(max,end-start +1) =2,繼續執行，end = 3+1 = 4， 如下圖：

判斷第5個字符e,hashmap中沒有包含e,這時將作為key存入map,下標4存入value中，max =Math.max(max,end-start +1) =3, 繼續執行，end = 4+1 = 4， 如下圖：

判斷第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，如下圖：

判斷end=6時，超出字串范圍，程式結束，所以最終字符的長度為3，

3、影片如下：

代碼實作

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

土哥的代碼均已經通過Leetcode在線測評，保證代碼是沒有問題，原創不易，各位覺得文章不錯的話，不妨點贊（在看）、留言、轉發三連走起！謝謝大家！

最近整理了一份計算機類的書籍，包含python、java、大資料、人工智能、演算法等，種類特別齊全，
獲取方式：關注公眾號：3分鐘秒懂大資料，回復：福利，就可以獲得這份超級大禮！