題目

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

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。
示例 3:

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

思路

滑動窗口

Java 實(shí)現(xiàn)

class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int lo=0,hi=-1;
        int retLen=0;
        int[] freq = new int[256];   //用來記錄出現(xiàn)窗口中字母的頻率
        while(lo<s.length()){    
                
            if(hi+1<s.length() && freq[s.charAt(hi+1)]==0){  //窗口右邊的字符不重復(fù)
                hi++;
                freq[s.charAt(hi)]++;
            }
            else{     //窗口右邊的字符重復(fù)  或  hi已經(jīng)到達(dá)邊界
                
                freq[s.charAt(lo)]--;
                lo++;
            }
            
            if(hi-lo+1>retLen)
                retLen=hi-lo+1;
        }
        return retLen;
        
    }

}