2020/2/18
题目描述
- 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
相关标签
哈希表
双指针
字符串
Sliding Window
解题思路
- 算法：使用一个Vec来存储char对应ACSII码(usize)与其第一次出现在字符串中index（O(1) 查询时间，vec长度为128，char出现的index设为-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转化为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
}
}
- 执行用时 :0 ms, 在所有 Rust 提交中击败了100.00%的用户
- 内存消耗 :2 MB, 在所有 Rust 提交中击败了97.29%的用户
总结
.chars()将&str转化为Chars(chars的迭代器)，用于从string以及str获取char的情况。
std::cmp::max()比较两个实现了Ord trait的同一类型变量。
