使用LeetCode怎么實現無重復字符的最長子串

本篇文章為大家展示了使用LeetCode怎么實現無重復字符的最長子串，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

描述

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

示例 1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。
  請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

示例 4:

輸入: s = ""
輸出: 0

0 <= s.length <= 5 * 104
s 由英文字母、數字、符號和空格組成

Solution

解法

暴力思路

檢查重復字符串的思路有哪些？

• 兩次遍歷循環字符串

• 存入之前判斷Set中是否已經存在字符串

• 計算最新的結果長度，并且將當前字符串存入到Set中

• 每當第二次循環完成之后，清空Set，防止影響下一個第一層循環的數據

• 有則BREAK，進入下一個外層循環

• 第一層循環記錄頭部信息

• 第二層循環用來滑動數據

• 將第二層數據存入到Set中

CODE

class Solution {
     public int lengthOfLongestSubstring(String s) {
       int res = 0 ;
       Set<Character> set = new HashSet<>();
       for(int i = 0 ; i < s.length();i++){
           for(int j = i ; j < s.length() ; j++){
               if(set.contains(s.charAt(j))){
                  break;
               }
               if(j-i+1 > res){
                   res = j-i+1;
               }
               set.add(s.charAt(j));
           }
           set.clear();
       }
       return res;
    }
}

復雜度

• 時間復雜度：O(N^2)，N 為S的長度

結果

• 執行用時：99 ms, 在所有 Java 提交中擊敗了12.37%的用戶

• 內存消耗：38.7 MB, 在所有 Java 提交中擊敗了39.62%的用戶

雙指針版本

解題思路

雙指針，又名滑動窗口，其實就是一個隊列，比如例題中的 abcabcbb，進入這個隊列（窗口）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！

1，從A ->ABC

當前Left為0，Right為2，整體的結果最大長度為3，緩存cache中已經有了數據{A:0,B:1,C:2}

2. ABCA

當再次遇到A時，緩存cache中已經存在了A字符串，我們需要比較【當前A在緩存中的位置】，與【當前Left的值】，如果Left的值小于等于A在緩存中的位置，那么我們需要調整Left的值為（A在緩存中的位置 + 1），這么做主要是為了Left坐標始終處于最新的重合點的位置的后面一位，組成新的不重合的長度

3. ABCAB

跟上面同理，當遇到B時，緩存中已經存在了B字符串，需要比較【當前B在緩存中的位置】，與【當前Left的值】，如果Left的值小于等于``B在緩存中的位置，那么久需要調整Left的值為（B在緩存中的位置+1），最終是為了Left坐標始終處于最新的重合點（B）的位置的后面一位，組成新的不重合的長度

CODE

class Solution {
     public int lengthOfLongestSubstring(String s) {
         
       int length = s.length();
       if(length == 0){
           return 0;
       }
       int res = 0 ;
       //快指針
       int right = 0 ;
       //慢指針 
       int left = 0 ;
       //索引，空間換時間
       Map<Character,Integer> map = new HashMap<>();
       for(;right<length;right++){
           Character c = s.charAt(right);
        if(map.containsKey(c)){
            //更新left
            if( map.get(c) >= left){
                    left = map.get(c)+1;
            }
        }
        //更新結果res
        if((right-left+1)>res){
                res = (right-left+1);
        }
         //更新c的位置
        map.put(c,right);

       }
       return res ;
    }
}

復雜度

• 時間復雜度：O(N)，N為字符串長度

結果

• 執行用時：7 ms, 在所有 Java 提交中擊敗了79.24%的用戶

• 內存消耗：38.8 MB, 在所有 Java 提交中擊敗了28.63%的用戶

上述內容就是使用LeetCode怎么實現無重復字符的最長子串，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。