從零開始刷Leetcode day02 無重複字元的最長子串(Longest Substring Without Repeating Characters)

無重複字元的最長子串(Longest Substring Without Repeating Characters)-java解法

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

Given a string, find the length of the longest substring without repeating characters.

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

示例1:

輸入: “abcabcbb”

輸出: 3

解釋: 因為無重複字元的最長子串是 “abc”，是以其長度為 3。

示例2:

輸入: “bbbbb”

輸出: 1

解釋: 因為無重複字元的最長子串是 “b”，是以其長度為 1。

暴力解法：

• 通過兩個for循環，算出每個字元開頭的不含有重複字元的 最長子串 的長度。

  時間複雜度： O(n²)

  代碼：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals("")||s.length() ==0){
            return 0;
        }if(s.equals(" ")||s.length() == 1){
            return 1;
        }int max = 1;
        for(int i =0;i<s.length();i++){
            Map<Character,Integer> map = new HashMap<>();
            map.put(s.charAt(i),0);
            int count = 1;
           for(int j =i+1;j<s.length();j++){
            if(map.containsKey(s.charAt(j))){
                break;
            }else{
                map.put(s.charAt(j),0);
                ++count;
            }}max = count>max? count:max;
        }return max;
    }
}
           

滑動視窗解法：

• 每次在[start，end]中如果有重複的，我們的做法是更新視窗從end重新開始，這種方法要求定義一個hashmap儲存字元到索引的映射，并且每次都會更新map的值
• 定義一個 map 資料結構存儲 (k, v)，其中 key 值為字元，value 值為字元位置 +1，加 1，表示從字元位置後一個才開始不重複

• 定義不重複子串的開始位置為 start，結束位置為 end

  随着 end 不斷周遊向後，會遇到與 [start, end] 區間内字元相同的情況，此時将字元作為 key 值，擷取其 value 值，并更新 start，此時 [start, end] 區間内不存在重複字元

• 無論是否更新 start，都會更新其 map 資料結構和結果 ans。

  代碼：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start =0;
        int res =0;
        Map<Character,Integer> map = new HashMap<>();
        for(int end =0;start<s.length() &&end<s.length();end++){
            if(map.containsKey(s.charAt(end))){
                start = Math.max(start,map.get(s.charAt(end))+1);
            }map.put(s.charAt(end),end);
                res = Math.max(end-start+1,res);
         }return res;
    }
}
           

說明：

start=Math.max(map.get(s.charAt(end)),start);判斷max的意義。

舉例字元串為pwwkewp，當我們檢查到最後一個p的時候，如果我們沒有判斷max的這個步驟，那麼start就會回到1的位置，是以說為了防止這種情況出現，需要使用max。