LeetCode 3 无重复字符的最长子串函数签名 pub fn length_of_longest_substring(s: String) - i32最优解法滑动窗口用数组记录字符最近一次下标O(n)时间O(1)空间适配ASCII字符。rustpub fn length_of_longest_substring(s: String) - i32 {let bytes s.as_bytes();// last_pos[c] 保存字符c上一次出现的索引初始为 -1let mut last_pos [-1i32; 128];let mut left 0i32;let mut max_len 0i32;for (idx, ch) in bytes.iter().enumerate() {let cur_idx idx as i32;let c ch as usize;// 当前字符在窗口内重复左边界跳到重复字符下一位if last_pos[c] left {left last_pos[c] 1;}last_pos[c] cur_idx;max_len max_len.max(cur_idx - left 1);}max_len}#[cfg(test)]mod tests {use super::*;#[test]fn test_case() {assert_eq!(length_of_longest_substring(abcabcbb.into()), 3);assert_eq!(length_of_longest_substring(bbbbb.into()), 1);assert_eq!(length_of_longest_substring(pwwkew.into()), 3);assert_eq!(length_of_longest_substring(.into()), 0);}}要点说明1. left 只向右移动不会回退每个字符仅遍历一次 O(n)2. 固定大小 [‑1;128] 数组空间复杂度 O(1)3. 兼容空字符串边界。如果输入包含完整Unicode非ASCII字符需要改用 HashMapchar,i32 版本需要我一并给出吗。
LeetCode 3 无重复字符的最长子串函数签名 pub fn length_of_longest_substring(s: String) - i32最优解法滑动窗口用数组记录字符最近一次下标O(n)时间O(1)空间适配ASCII字符。rustpub fn length_of_longest_substring(s: String) - i32 {let bytes s.as_bytes();// last_pos[c] 保存字符c上一次出现的索引初始为 -1let mut last_pos [-1i32; 128];let mut left 0i32;let mut max_len 0i32;for (idx, ch) in bytes.iter().enumerate() {let cur_idx idx as i32;let c ch as usize;// 当前字符在窗口内重复左边界跳到重复字符下一位if last_pos[c] left {left last_pos[c] 1;}last_pos[c] cur_idx;max_len max_len.max(cur_idx - left 1);}max_len}#[cfg(test)]mod tests {use super::*;#[test]fn test_case() {assert_eq!(length_of_longest_substring(abcabcbb.into()), 3);assert_eq!(length_of_longest_substring(bbbbb.into()), 1);assert_eq!(length_of_longest_substring(pwwkew.into()), 3);assert_eq!(length_of_longest_substring(.into()), 0);}}要点说明1. left 只向右移动不会回退每个字符仅遍历一次 O(n)2. 固定大小 [‑1;128] 数组空间复杂度 O(1)3. 兼容空字符串边界。如果输入包含完整Unicode非ASCII字符需要改用 HashMapchar,i32 版本需要我一并给出吗。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
