題目:

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

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

示例 1:

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

示例 2:

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

示例 3:

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

解題思路:

• 暴力求解, 時間復(fù)雜度為 O(n^3), 因為要對所有字符遍歷, 對子串遍歷確認是否有重復(fù)字符, pass

• 滑動窗口, 維護一個索引 [i,j) 的滑動窗口, 對已存在的字符 i' 直接更新滑動窗口 [i',j), 你需要保留每一個字符值及其索引, 即由字符映射索引位置

  • 哈希映射: Key 為字符值, Value 為索引位置
  • 字符映射: ASCII 碼共 128 個字符, 維護一個長度為 128 的整型數(shù)組,數(shù)組索引值映射 128 個字符,存儲元素值為字符位置

哈希映射:

Java:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();//轉(zhuǎn)為字符數(shù)組
        if (chars.length == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();//建立哈希映射
        int size = s.length(), count = 0, i = 0;
        for (int j = 0; j < size; j++) {//遍歷字符
            if (map.containsKey(chars[j]))//如果映射中存在該字符
                i = Math.max(map.get(chars[j]), i);//更新滑動窗口的左邊界 i
            count = Math.max(count, j - i);//更新 count 為最大值
            map.put(chars[j], j + 1);//更新映射中該字符映射的 Value 值為當前位置加一
        }
        return count + 1;//返回最大累加總數(shù), 需要加 1
    }
}

Python:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        hash_map = dict() # 建立字典
        size = len(s)
        i, count = 0, 0
        for j, c in enumerate(s): # 枚舉字符
            if c in hash_map: # 如果映射中存在該字符
                i = max(i, hash_map[c]) # 更新滑動窗口的左邊界 i
            count = max(count, j-i) # 更新 count 為最大值
            hash_map[c] = j+1 # 更新映射中該字符映射的 Value 值為當前位置加一
        return count+1 # 返回最大累加總數(shù), 需要加 1

字符映射:

Java:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        int[] index = new int[128];//建立長度為 128 位的 ASCII 碼字符映射表
        int size = s.length(), count = 0, i = 0;
        for (int j = 0; j < size; j++) {//遍歷字符
            i = Math.max(index[chars[j]], i);//更新滑動窗口的左邊界 i
            count = Math.max(count, j - i);//更新 count 為最大值
            index[chars[j]] = j + 1;//更新映射中該字符所在元素值為當前位置加一
        }
        return count + 1;//返回最大累加總數(shù), 需要加 1
    }
}

Python:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        size = len(s)
        i, count = 0, 0
        index = [0]*128 # 建立長度為 128 位的 ASCII 碼字符映射表
        for j, c in enumerate(s): # 枚舉字符
            i = max(i, index[ord(c)]) # 更新滑動窗口的左邊界 i
            count = max(count, j-i) # 更新 count 為最大值
            index[ord(c)] = j+1 # 更新映射中該字符所在元素值為當前位置加一
        return count+1 # 返回最大累加總數(shù), 需要加 1

因為 Python 沒有字符概念, 需要 ord() 函數(shù)轉(zhuǎn)為 ASCII 數(shù)字

歡迎關(guān)注微.信公..眾.號: 愛寫B(tài)ug

愛寫B(tài)ug.jpeg