【算法学习】四、无重复字符的最长子串（Rust 解法）

Algorithms
, ,

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

示例

1
2
3
4
5
6
7
8
9
10
11
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

滑动窗口解法

思路分析

使用滑动窗口，维护一个不含重复字符的窗口。窗口用两个指针 start 和 end 表示，使用 HashSet 来记录窗口中的字符。

  1. 初始化 start = 0，end = 0，max_length = 0
  2. 如果 s[end] 不在集合中，将其加入集合，扩大窗口
  3. 如果 s[end] 已经在集合中，移除 s[start] 并缩小窗口
  4. 重复步骤 2-3 直到 end 到达字符串末尾

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
use std::collections::HashSet;

struct Solution;

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut max_length: i32 = 0;
        let chars: Vec<char> = s.chars().collect();
        let (mut start, mut end) = (0, 0);
        let mut unique_chars = HashSet::new();
        
        while end < chars.len() {
            if !unique_chars.contains(&chars[end]) {
                unique_chars.insert(&chars[end]);
                end += 1;
                max_length = max_length.max(unique_chars.len() as i32);
            } else {
                unique_chars.remove(&chars[start]);
                start += 1;
            }
        }
        max_length
    }
}

fn main() {
    println!(
        "{}",
        Solution::length_of_longest_substring("pwwkew".to_string())
    );
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问两次（一次被 end 指针，一次被 start 指针）。
  • 空间复杂度：O(min(m, n))，其中 m 是字符集的大小。在题目中，m 通常是一个常数（ASCII 字符集为 128，Unicode 可能更大）。

算法演示

以字符串 "abcabcbb" 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
初始状态：start = 0, end = 0, max_length = 0, unique_chars = {}

1. end = 0: 'a' 不在集合中
   unique_chars = {'a'}, end = 1, max_length = 1

2. end = 1: 'b' 不在集合中
   unique_chars = {'a', 'b'}, end = 2, max_length = 2

3. end = 2: 'c' 不在集合中
   unique_chars = {'a', 'b', 'c'}, end = 3, max_length = 3

4. end = 3: 'a' 已在集合中
   unique_chars.remove('a'), start = 1
   unique_chars = {'b', 'c'}

5. end = 3: 'a' 不在集合中
   unique_chars = {'b', 'c', 'a'}, end = 4, max_length = 3

6. end = 4: 'b' 已在集合中
   unique_chars.remove('b'), start = 2
   unique_chars = {'c', 'a'}

...继续直到 end 到达末尾