LeetCode 力扣 3.無重複字元的最長子串

題目：

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例 1: 輸入: “abcabcbb” 輸出: 3 解釋: 因為無重複字元的最長子串是 “abc”，是以其長度為 3。

示例 2: 輸入: “bbbbb” 輸出: 1 解釋: 因為無重複字元的最長子串是 “b”，是以其長度為 1。

示例 3: 輸入: “pwwkew” 輸出: 3 解釋: 因為無重複字元的最長子串是 “wke”，是以其長度為 3。

請注意，你的答案必須是 子串 的長度，“pwke” 是一個子序列，不是子串。

從示例 3 可以看出來，子串必須是連續的。

一、分析

分析：

1. “滑動視窗”的思想比較容易想到，用兩個指針 i 和 j；
2. 将 i 固定在開始，j 移動，如果沒有重複則繼續移動 j ，一旦重複就記錄距離，這是一個“無重複字元”的子串的長度；
3. 接着 i 就可以直接跳到 j 的位置（因為 j 是重複元素），j 繼續移動，重複上面的過程，更新每次的子串的長度。

具體的實作來說：

1. 如果使用清單，在查找“有沒有重複”的過程裡，一般是要周遊前面已有的所有位置，那麼在總共的兩重循環下，時間複雜度會達到 O(n) ，好處是在找到重複之後就立刻知道重複的元素是誰，可以将 i 跳到 j ；
2. 如果查找“有沒有重複”的過程希望複雜度位 O(1) 那麼可以使用哈希表，但是哈希表的存儲一般沒有順序，沒法按下标，是以 i 的挪動隻能“按值”将最早加入哈希表的那個字元删掉，也就是子串的最前面一個字元，這樣外循環是連續的 O(n) ；
3. 讓哈希表也能删除連續的好幾個元素。

二、做法一（HashSet）

直接利用資料結構 HashSet ，我們以示例 1 來模拟過程，“abcabcbb”，要找出最長的子串：

“a b c a b c b b”

1. a，加入集合；
2. b，加入集合；
3. c，加入集合；
4. a，已經有 a 了，重複，此時子串最大長度是 3 。從集合删除最前面的 a ，此時剩下 b c；
5. a，加入集合；
6. b，已有 b ，重複，此時最長長度為 b c a 是3。從集合中删除最前面的 b ，此時剩下 c a；
7. b，加入集合；
8. c，已有 c ，重複，此時最長長度為 c a b 是3。從集合中删除最前面的 c，此時剩下 a b；
9. c，加入集合；
10. b，已有 b，重複，此時最大長度為 a b c 是3。（雖然我們希望從集合中直接删除 a 和 b，畢竟直接從 c 開始才有意義。但是由于 set 無法記錄下标，辦不到，隻能移除一個最前面的 a ，然後繼續進行判斷）。從集合中删除 a，此時剩下 b c；
11. b，已有 b，重複，此時最大長度是 b c 是2。從集合中删除 b，剩下 c；
12. b，加入集合；
13. b，已有 b，重複，此時最大長度是 c b 是2。從集合中删除 c，剩下 b（注意，仍然沒辦法直接删完）；
14. b，已有 b，重複，删除 b ，删除後集合已經空；
15. b，加入集合。

代碼做法很簡單：

• 外循環直接周遊字元串一次。
• 内部先判斷是否重複，如果重複，删除 Set 裡最前面（邏輯上最前面）的一個元素。

我們需要額外的一個指針，周遊字元串的 i 是其中的一個，總是代表子串的開始，還需要一個 end 指針代表子串的最右邊。

//對于整個s周遊一遍，時間複雜度為 O(n) 。
        for(int i=0;i<s.length();i++){
            if(i>0){
                set.remove(s.charAt(i-1));
            }
            
            //最右邊出現重複元素之後 end 還要後移，避免超範圍用 end+1 來判斷
            while(end+1<s.length() && !set.contains(s.charAt(end+1))){
                set.add(s.charAt(end+1));
                end++;
            }
            //更新ans，用下标之差來計算，由于上一步判斷用的是 end+1 是以距離要+1.
            ans=Math.max(ans,end-i+1);
        }
           

加上初始化和特殊情況的判斷，就可以寫出完整代碼.

ans 的初始值顯然為 0，那麼 end 的初始值應該為 0 嗎？

考慮到開始 Set 為空，那麼第一次執行 add 操作的時候， add( end+1 ) 加進去的是下标為 0 的字元，是以end的初始值應該設為 -1。

完整代碼：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==1){
            return 1;
        }
        Set<Character> set=new HashSet<>();
        int ans=0;
        int end=0;

        for(int i=0;i<s.length();i++){
            if(i>0){
                set.remove(s.charAt(i-1));
            }

            while(end+1<s.length() && !set.contains(s.charAt(end+1))){
                set.add(s.charAt(end+1));
                end++;
            }
            ans=Math.max(ans,end-i+1);
        }
        return ans;
    }
}
           

三、利用ASCII碼值建立哈希數組

上一種方法的弊端我們已經讨論過，對于子串的開始指針 i 和結束指針 j ，找到重複之後就立刻知道重複的元素是誰，可以将 i 跳到 j，這一點做不到。

考慮到 ASCII 碼值總共隻有 128 個，是以我們可以用對應的碼值，也就是 charAt(i) 作為下标，自己建立一個哈希表，用數組的值記錄 “ 某一個字元出現過的次數 ” ：

• 在“查找是否重複”的時候，根據下标取值，判讀是否為 1 ，時間為 O(1) ；
• 删除的時候，要把 i 直接挪到 j，可以用 i 和 j 之間每一個 charAt(i) ，找到數組中的值然後 -1 ，這樣也是 O(1) 的時間複雜度，并且一次删除了所有多餘的數字， i 的下一個開始位置就是 j 。

如果閱讀起來不容易，可以直接來看代碼：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] hashmap=new int[128];
        int ans=0;
        int n = s.length();

        for(int i=0,end=0;end<n;end++){
            hashmap[s.charAt(end)]++;

			//隻要 i 還沒有到 end ，中間的這段字元都删除，也就是哈希表中的值 --
			//while 結束的時候，i 到達 end 也就是上一個重複字元
            while(hashmap[s.charAt(end)]>1){
                hashmap[s.charAt(i)]--;
                i++;
            }

            ans=Math.max(ans,end-i+1);//目前這個不重複子串的長度和已有ans取最大值
        }
        return ans;
    }
}
           

這段代碼的核心就是 while 部分，假如是 “ a b c d c ” 的話：

• hashmap[ a ]++, hashmap[ b ]++, hashmap[ c ]++, hashmap[ d ]++，ans一路增加到了 4 ，這段時間起始的 i 都沒變;
• end = c，發現了重複，展現在 hashmap[ c ]=2>1 了，進入while循環：
  • hashmap[ a ]- -，發現 hashmap[ c ]沒變化，還是=2>1
  • hashmap[ b ]- -，發現 hashmap[ c ]沒變化，還是=2>1
  • hashmap[ c ]- - ，發現hashmap[ c ]變化了，1 不再 >1
  • i 更新到了 end 在的位置
• 繼續下一個子串，開始就是 i 在 end 的位置