LeetCode 3. 无重复字符的最长子串

2026-09-09 HGNULB 约 3 分钟

文章信息 29 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决已掌握 500+ 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东华为拼多多网易小米亚马逊虾皮图森携程哔哩哔哩小红书陌陌 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 3. 无重复字符的最长子串

题意分析

给定字符串 s，求其中不含重复字符的最长连续子串的长度，返回长度而不是子串本身。

两个关键词决定了算法形态。“连续”说明答案对应原串上的一段区间 [left, right]，可以用两个下标刻画；“无重复”则是一个对区间单调的性质：若 [left, right] 内无重复，它的任意子区间也无重复；反过来，一旦区间内出现重复，继续向右扩张永远不可能重新合法，只能先收缩左边界。这正是可变长滑动窗口成立的条件。

于是问题可以改写成：对每个右端点 right，求出使 [left, right] 无重复的最小 left，答案就是所有 right - left + 1 的最大值。这样枚举右端点一遍即可，不必枚举所有子串。

边界情况：s 为空时答案是 0；s 全部字符相同（如 "bbbbb"）时答案是 1；s 本身就无重复时答案是整串长度。

解法：滑动窗口 + 最近出现位置

核心思路

用 left 维护当前无重复窗口的左边界，数组记录每个字符最近一次出现位置的下一位。遇到重复字符时，left 只能右移，不能回退。

解题步骤

从左到右遍历字符串，right 是窗口右边界。

将 left 更新为 max(left, last[s[right]])。

用 right - left + 1 更新最长长度。

记录当前字符下一次允许出现的位置 right + 1。

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        int left = 0, ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            left = Math.max(left, last[ch]);
            ans = Math.max(ans, right - left + 1);
            last[ch] = right + 1;
        }
        return ans;
    }
}

func lengthOfLongestSubstring(s string) int {
    var last [128]int
    left, ans := 0, 0

    for right := 0; right < len(s); right++ {
        if last[s[right]] > left {
            left = last[s[right]]
        }
        if length := right - left + 1; length > ans {
            ans = length
        }
        last[s[right]] = right + 1
    }
    return ans
}

复杂度分析

时间复杂度：$O(n)$，每个字符只处理一次。

空间复杂度：$O(\lvert\Sigma\rvert)$，字符集大小固定时为 $O(1)$。

关键点总结

表中存“下标 + 1”，默认值 0 就能表示未出现。

左边界取最大值，避免被窗口外的重复字符拉回。

更新答案后再覆盖字符的最近位置。

易错点总结

直接令 left = last[ch]，会让左边界回退。

忘记 + 1，会把窗口长度少算一位。

本实现按题目字符范围使用长度为 128 的数组；字符集不确定时改用哈希表。

相似题目

题目	难度	考察点
159. 至多包含两个不同字符的最长子串	中等	判非法条件换成窗口内字符种类超过 2
340. 至多包含 K 个不同字符的最长子串	中等	种类上限推广为 k，计数写法可直接复用
424. 替换后的最长重复字符	中等	合法条件变为「窗口长度 - 最高频次 ≤ k」
1004. 最大连续 1 的个数 III	中等	只对 0 计数，窗口内 0 的个数不超过 k
992. K 个不同整数的子数组	困难	恰好 k 种，拆成「至多 k」减「至多 k-1」
LCR 016. 无重复字符的最长子串	中等	与本题同题，可直接套用两种写法
剑指 Offer 48. 最长不含重复字符的子字符串	中等	与本题同题，另可用「以 i 结尾」的 dp 视角推导