LeetCode 补拙笔记

0. 前言

• 日期：2026.06.09
• 题目：3. 无重复字符的最长子串
• 难度：中等
• 标签：滑动窗口、哈希表

1. 题目理解

问题描述： 给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

示例：

输入：s = "abcabcbb" 输出：3 解释：无重复字符的最长子串是 "abc"，长度为 3。

2. 解题思路

核心观察

• 用滑动窗口 [left, right] 表示当前无重复字符的子串。
• 窗口右边界 right 不断右移，遇到重复字符时，将左边界 left 移动到重复字符上一次出现位置的下一位，保证窗口内无重复字符。

算法步骤

1. 初始化左指针 left = 0，结果 max = 0，以及记录字符上一次出现位置的数组 last；
2. 遍历字符串，移动右指针 right；
3. 遇到重复字符，更新左指针 left；
4. 更新当前窗口长度，更新全局最大值；
5. 记录当前字符的最新位置。

3. 代码实现

package lc0_lc99.lc3;

import java.util.HashSet;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<String> set = new HashSet<>();
        int res = 0;
        int curRes = 0;
        int leftPos = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            String s1 = String.valueOf(c);
            while (set.contains(s1)) {
                set.remove(String.valueOf(s.charAt(leftPos)));
                leftPos++;
                curRes--;
            }
            set.add(s1);
            curRes++;
            res=Math.max(curRes,res);
        }
        return res;
    }
}

4. 代码优化说明

class Solution {
public int lengthOfLongestSubstring(String s) {
    // 用数组记录每个字符上一次出现的位置，初始为0
    int[] last = new int[128];
    int max = 0;
    int left = 0;
    for(int right = 0; right < s.length(); right++){
        char c = s.charAt(right);
        // 更新左边界：取当前左边界和字符上次出现位置+1的较大值
        left = Math.max(left,last[c]);
        // 更新当前窗口长度，并记录最大值
        max = Math.max(max,right-left+1);
        // 更新字符最新出现位置为right+1，避免后续重复计算
        last[c] = right+1;
    }
    return max;
}
}

5. 复杂度分析

• HashSet 滑动窗口版
  • 时间复杂度：$O(n)$，左右指针最多各移动 n 次。
  • 空间复杂度：$O(k)$，k 为字符集大小，最坏情况为 $O(n)$。
• 数组优化版
  • 时间复杂度：$O(n)$，单次遍历。
  • 空间复杂度：$O(1)$，固定大小的数组 int[128]，与输入长度无关。

6. 总结

• 核心：滑动窗口思想，用左右指针维护无重复字符的窗口。
• 优化亮点：
  1. 用 int[128] 数组代替 HashSet，读写操作更高效；
  2. 去掉了 while 循环，用 Math.max 直接更新左指针，代码更简洁；
  3. 一次遍历完成所有操作，效率更高。
• 关键：通过 last[c] = right + 1 巧妙处理了字符重复时左边界的移动。