題目:
給定一個字元串,請你找出其中不含有重複字元的 最長子串 的長度。
Given a string, find the length of the longest substring without repeating characters.
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字元的最長子串是 "abc",是以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重複字元的最長子串是 "b",是以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重複字元的最長子串是 "wke",是以其長度為 3。
請注意,你的答案必須是 子串 的長度,"pwke" 是一個子序列,不是子串。
解題思路:
- 暴力求解, 時間複雜度為 O(n^3), 因為要對所有字元周遊, 對子串周遊确認是否有重複字元, pass
- 滑動視窗, 維護一個索引
的滑動視窗, 對已存在的字元[i,j)
直接更新滑動視窗i'
, 你需要保留每一個字元值及其索引, 即由字元映射索引位置[i',j)
- 哈希映射: Key 為字元值, Value 為索引位置
- 字元映射: ASCII 碼共 128 個字元, 維護一個長度為 128 的整型數組,數組索引值映射 128 個字元,存儲元素值為字元位置
哈希映射:
Java:
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray();//轉為字元數組
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;//傳回最大累加總數, 需要加 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 # 傳回最大累加總數, 需要加 1
字元映射:
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;//傳回最大累加總數, 需要加 1
}
}
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 # 傳回最大累加總數, 需要加 1
因為 Python 沒有字元概念, 需要
ord()
函數轉為 ASCII 數字
歡迎關注微.信.公..衆.号: 愛寫Bug