无重复字符的最长子串 - Rust

image.png

题目解析
采用滑动窗口。

pub fn length_of_longest_substring(s: String) -> i32 {
    use std::collections::HashMap;
    
    if s.len() == 0{
        return 0 ;
    }
    let mut map = HashMap::with_capacity(s.len());
    let s = s.chars().collect::<Vec<_>>();
    let mut max = 0;
    let mut left = 0;

    s.iter().enumerate().for_each(|(index,char)|{
        if let Some(last) = map.get(char) {
            left = std::cmp::max(left, *last);
        }
        max = std::cmp::max(max, index - left + 1);
        map.insert(*char, index + 1);
    });
 
    max as i32
}


#[cfg(test)]
mod tests {
    #[test]
    fn length_of_longest_substring_test() {
        use super::length_of_longest_substring;

        let s = String::from("afebcfefx");
        assert_eq!(5, length_of_longest_substring(s));
    }
}

复杂度分析
空间复杂度: O(n)。
时间复杂度: O(n)。