0003. 无重复字符的最长子串 Longest Substring Without Repeating Characters

问题描述

这类问题, 可以优先考虑使用滑动窗口, 因为要找最长无重复的子串, 可以在窗口内维护那个子串, 然后将窗口右侧向右移, 如果条件不满足, 就把窗口左侧边界向右移, 直到满足条件为止.

代码实现:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// 滑动窗口法
// 使用HashMap 来缓存窗口内的所有字符, 加快查找
pub fn length_of_longest_substring2(s: String) -> i32 {
    // 当窗口右侧经过一个字符时, 要检查它是不是在窗口内.
    // 如果不在窗口内, 则继续当窗口右侧右移;
    // 如果在窗口内了, 说明需要将窗口左侧向右移, 直到遇到相同的字符.
    // 然后计算最长的那个窗口.

    // (字符, 字符在字符串中的位置)
    let mut map = HashMap::<u8, usize>::new();
    let bytes = s.as_bytes();

    let mut substring_max_len = 0;
    let mut left = 0;
    let mut right = 0;

    // 遍历所有字符.
    while right < bytes.len() {
        if let Some(&index) = map.get(&bytes[right]) {
            while left <= index {
                map.remove(&bytes[left]);
                left += 1;
            }
        }

        // 将窗口右侧字符加进去.
        map.insert(bytes[right], right);
        right += 1;

        // 并更新最大字串.
        substring_max_len = substring_max_len.max(map.len());
    }

    // 返回结果
    substring_max_len as i32
}
}