題目

• 3. 無重復(fù)字符的最長子串 - 力扣（LeetCode）

簡述

• 給到我們一個字符串, 要求返回其最長無重復(fù)子串的長度, 注意是最長子串, 而不是子序列

分析

• 在沒學(xué)到哈希表之前, 我苦想于該如何判斷重復(fù)并停止加入集合中, 本想直接用StringBuilder進行拼接第一個字符, 然后將StringBuilder轉(zhuǎn)換成String對象, 繼續(xù)對新的字符串遍歷判斷下一個原字符串中的字符是否重復(fù)于StringBuilder中的字符, 但是這樣做只能返回其無重復(fù)的子序列.
• 在有了哈希表之后, 判斷重復(fù)就簡單了許多.
• 如果我們有兩個指針, 一個在用來記錄無重復(fù)子串的開始, 另一個指針不斷向右移動, 直到遇到有重復(fù)的元素為止, 然后我們將該子串的長度記錄, 再將左指針右移一次, 此時兩指針內(nèi)的子串一定是無重復(fù)的, 再判斷右指針是否該右移, 但注意左指針左移后, 需要將前一個字符在哈希表中刪除

代碼如下

public int lengthOfLongestSubstring(String s) {
                //先創(chuàng)建一個HashSet
                HashSet<Character> hs = new HashSet<>();
                //max用于后續(xù)記錄子串的長度
                int max = 0;
                //用作右指針, 初始值為-1是因為我們的右指針?biāo)傅淖址且呀?jīng)存入集合中的
                //我們需要判斷右指針下一個字符即(end+1)是否重復(fù)于集合所存的字符
                //所以需要初始值為-1, 因為我們要將字符串中0索引的字符添加到集合中
                int end = -1;
                //遍歷字符串, i就可以作為左指針, 我們在for循環(huán)中將右指針的操作全部完成
                //即已經(jīng)找到了一個無重復(fù)子串, 并且記錄了子串的長度
                //做完這些, 就可以將左指針左移
                for (int i = 0; i < s.length(); i++) {
                    //由于每次移動左指針都需要將上一個字符刪除
                    //所以只要左指針不為0, 則說明已經(jīng)需要將上一個字符刪除了
                    if (i != 0) hs.remove(s.charAt(i - 1));
                    //為了確保右指針做完所有事情, 所以用while循環(huán)
                    //循環(huán)條件是右指針的下一個字符不超過字符串的長度, 并且下一個字符沒有和集合中的字符重復(fù)
                    while (end + 1 < s.length() && !hs.contains(s.charAt(end + 1))) {
                        //符合條件則將下一個字符添加到集合中
                        hs.add(s.charAt(end + 1));
                        //不斷移動右指針, 直到條件不符合
                        end++;
                    }
                    //記錄集合中的子串長度, 然后將其于下一個子串的長度對比, 取最大值
                    max = Math.max(max, end + 1 - i);
                }
                return max;
            }