使用LeetCode怎么實(shí)現(xiàn)無(wú)重復(fù)字符的最長(zhǎng)子串

本篇文章為大家展示了使用LeetCode怎么實(shí)現(xiàn)無(wú)重復(fù)字符的最長(zhǎng)子串，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

描述

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
  請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

示例 4:

輸入: s = ""
輸出: 0

0 <= s.length <= 5 * 104
s 由英文字母、數(shù)字、符號(hào)和空格組成

Solution

解法

暴力思路

檢查重復(fù)字符串的思路有哪些？

• 兩次遍歷循環(huán)字符串

• 存入之前判斷Set中是否已經(jīng)存在字符串

• 計(jì)算最新的結(jié)果長(zhǎng)度，并且將當(dāng)前字符串存入到Set中

• 每當(dāng)?shù)诙窝h(huán)完成之后，清空Set，防止影響下一個(gè)第一層循環(huán)的數(shù)據(jù)

• 有則BREAK，進(jìn)入下一個(gè)外層循環(huán)

• 第一層循環(huán)記錄頭部信息

• 第二層循環(huán)用來(lái)滑動(dòng)數(shù)據(jù)

• 將第二層數(shù)據(jù)存入到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;
    }
}

復(fù)雜度

• 時(shí)間復(fù)雜度：O(N^2)，N 為S的長(zhǎng)度

結(jié)果

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

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

雙指針版本

解題思路

雙指針，又名滑動(dòng)窗口，其實(shí)就是一個(gè)隊(duì)列，比如例題中的 abcabcbb，進(jìn)入這個(gè)隊(duì)列（窗口）為 abc 滿足題目要求，當(dāng)再進(jìn)入 a，隊(duì)列變成了 abca，這時(shí)候不滿足要求。所以，我們要移動(dòng)這個(gè)隊(duì)列！

1，從A ->ABC

當(dāng)前Left為0，Right為2，整體的結(jié)果最大長(zhǎng)度為3，緩存cache中已經(jīng)有了數(shù)據(jù){A:0,B:1,C:2}

2. ABCA

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

3. ABCAB

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

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 ;
       //索引，空間換時(shí)間
       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;
            }
        }
        //更新結(jié)果res
        if((right-left+1)>res){
                res = (right-left+1);
        }
         //更新c的位置
        map.put(c,right);

       }
       return res ;
    }
}

復(fù)雜度

• 時(shí)間復(fù)雜度：O(N)，N為字符串長(zhǎng)度

結(jié)果

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

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

上述內(nèi)容就是使用LeetCode怎么實(shí)現(xiàn)無(wú)重復(fù)字符的最長(zhǎng)子串，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。