无重复字符的最长子串 - Stellar Observer Protocol

649 字

3 分钟

无重复字符的最长子串

2025-08-23

Algorithms

字符串

/

哈希表

/

滑动窗口

题目描述#

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

解题思路#

滑动窗口法：
- 使用双指针维护当前无重复子串的窗口
- 右指针遍历字符串扩展窗口
- 左指针在发现重复时收缩窗口
字符位置映射：
- 哈希表记录字符最后出现位置
- 快速定位重复字符位置
窗口大小更新：
- 计算当前窗口长度 (right - left + 1)
- 动态更新最大子串长度
边界处理：
- 左指针跳跃避免无效移动
- 处理空串和单字符情况

关键洞察#

位置映射优化：
- 哈希表存储字符索引实现O(1)查找
- 左指针直接跳转到重复字符后一位
线性时间复杂度：
- 左右指针各遍历一次字符串
- 避免O(n²)的暴力解法
字符集无关性：
- 算法适用于ASCII和Unicode字符
- 空间复杂度由字符种类决定
窗口动态维护：
- 始终保证窗口内无重复字符
- 高效计算最大无重复区间

复杂度分析#

指标	说明
时间复杂度	O(n)：每个字符被访问最多两次
空间复杂度	O(k)：k为字符集大小（ASCII为128）
最优情况	O(n)：当字符串无重复字符时

代码实现#

1
/**
2
 * @param {string} s
3
 * @return {number}
4
 */
5
var lengthOfLongestSubstring = function (s) {
6

7
    if (s.length === 0) return 0
8

9
    let answer = 1;
10
    const map = {};
11

12
    let left = 0, right = 0;
13

14
    while (left <= right && right < s.length ) {
15
        const leftChar = s[left];
16
        const rightChar = s[right];
17
        if (!map[rightChar]) {
18
            map[rightChar] = true;
19
            answer = Math.max(answer, right - left + 1);
20
            right++;
21
        } else {
22
            map[leftChar] = false;
23
            left++;
24
        }
25
    }
26

27
    return answer;
28
};