2020/2/18
題目描述
- 給定一個字符串搅幅，請你找出其中不含有重復字符的 最長子串 的長度唉韭。
示例
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"削锰，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1问词。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"森爽，所以其長度為 3恨豁。
請注意，你的答案必須是 子串 的長度爬迟，"pwke" 是一個子序列橘蜜，不是子串。
相關(guān)標簽
哈希表
雙指針
字符串
Sliding Window
解題思路
- 算法：使用一個Vec來存儲char對應(yīng)ACSII碼(usize)與其第一次出現(xiàn)在字符串中index（O(1) 查詢時間付呕，vec長度為128计福，char出現(xiàn)的index設(shè)為-1）。然后遍歷字符串徽职，將每一個新遇到的字符的在vec中存儲的index與當前子序列的開頭索str_s引作比較象颖，若字符index大于str_s，則當此字符前一字符為止姆钉，獲得了一個無重復字符最長子序列说订，更新str_s到vec[char]+1以及子串最大length。每一次遍歷都對vec進行更新育韩。對(char, index)的存儲也可以使用hashmap克蚂。
- 復雜度分析
時間復雜度：O(n)，索引 j 將會迭代 n 次筋讨。
空間復雜度（HashMap）：O(min(m, n))埃叭，m 是字符集的大小。
空間復雜度（Table）：O(m)悉罕，m 是字符集的大小赤屋。
源代碼
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
if(&s == ""){
return 0 as i32;
}
let s = &s.trim();
let (mut str_s, mut str_e, mut length, mut result) = (0, 0, 0, 0);
let mut char_map: Vec<i32> = vec![-1;128];
let str_len = s.len();
if(str_len <= 1){
return 1 as i32;
}
while(str_e < str_len){
let mut cur_char = '0';
// .chars將&str轉(zhuǎn)化為Chars(chars的迭代器)
for c in s[str_e..str_e+1].chars(){
cur_char = c;
}
let cur_char_index = cur_char as usize - 0 as usize;
// println!("The current char is {}, converted index is {}.", cur_char, cur_char_index);
if(char_map[cur_char_index] >= str_s as i32){
str_s = (char_map[cur_char_index]+1) as usize;
length = (str_e - str_s) as i32;
}
char_map[cur_char_index] = str_e as i32;
length += 1;
str_e += 1;
result = std::cmp::max(length, result);
// println!("The str_e is {}, length is {}, result is {}.", str_e, length, result);
}
result
}
}
- 執(zhí)行用時 :0 ms, 在所有 Rust 提交中擊敗了100.00%的用戶
- 內(nèi)存消耗 :2 MB, 在所有 Rust 提交中擊敗了97.29%的用戶
總結(jié)
.chars()將&str轉(zhuǎn)化為Chars(chars的迭代器)立镶，用于從string以及str獲取char的情況。
std::cmp::max()比較兩個實現(xiàn)了Ord trait的同一類型變量类早。
