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

Categories:

Tags:

题目描述
思路分析
1. 解法一：滑动窗口 + 位置跳跃法（推荐）
2. 解法二：滑动窗口 + 删除法
相似题目

题目描述

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

题目：

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

示例 1：

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

示例 2：

输入：s = "bbbbb"
输出：1
解释：最长无重复子串为 "b"，长度为 1。

示例 3：

输入：s = "pwwkew"
输出：3
解释：最长无重复子串为 "wke"，长度为 3（注意 "pwke" 是子序列而非子串）。

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

思路分析

解法一：滑动窗口 + 位置跳跃法（推荐）

核心思路：

用哈希表记录每个字符最近出现的位置。

维护窗口 [left, right]，当 s[right] 在窗口内重复时，left 直接跳到 last + 1，避免一步步移动。

每次扩展右指针并更新最长长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(k)，其中 k 表示字符集大小（ASCII 约 128）。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        Map<Character, Integer> last = new HashMap<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last.containsKey(c)) {
                // 若重复字符仍在窗口内，左边界直接跳过
                left = Math.max(left, last.get(c) + 1);
            }
            last.put(c, right);
            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

func lengthOfLongestSubstring(s string) int {
	left := 0
	ans := 0
	last := make(map[byte]int)

	for right := 0; right < len(s); right++ {
		c := s[right]
		if idx, ok := last[c]; ok && idx >= left {
			// 若重复字符仍在窗口内，左边界直接跳过
			left = idx + 1
		}
		last[c] = right
		if right-left+1 > ans {
			ans = right - left + 1
		}
	}

	return ans
}

解法二：滑动窗口 + 删除法

核心思路：

维护一个不含重复字符的窗口和一个集合。

右指针扩展时若遇到重复字符，持续移动左指针并从集合中删除，直到冲突消除。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度，每个字符最多进出窗口一次。

空间复杂度：O(k)，其中 k 表示字符集大小。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        Set<Character> window = new HashSet<>();
        int left = 0;
        int right = 0;
        int ans = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            while (window.contains(c)) {
                // 遇到重复字符，左指针收缩直到消除冲突
                window.remove(s.charAt(left));
                left++;
            }
            window.add(c);
            ans = Math.max(ans, right - left + 1);
            right++;
        }

        return ans;
    }
}

func lengthOfLongestSubstring(s string) int {
	window := make(map[byte]bool)
	left := 0
	right := 0
	ans := 0

	for right < len(s) {
		c := s[right]
		for window[c] {
			// 遇到重复字符，左指针收缩直到消除冲突
			delete(window, s[left])
			left++
		}
		window[c] = true
		if right-left+1 > ans {
			ans = right - left + 1
		}
		right++
	}

	return ans
}

相似题目

题目	难度	考察点
159. 至多包含两个不同字符的最长子串	中等	滑动窗口
340. 至多包含 K 个不同字符的最长子串	中等	滑动窗口
992. K 个不同整数的子数组	困难	滑动窗口
1695. 删除子数组的最大得分	中等	滑动窗口
2260. 必须拿起的最小连续卡牌数	中等	滑动窗口、哈希表
2401. 最长优雅子数组	中等	滑动窗口、位运算
2405. 子字符串的最优划分	中等	滑动窗口、哈希表
2799. 统计完全子数组的数目	中等	滑动窗口、哈希表
2981. 找出出现至少三次的最长特殊子字符串 II	中等	滑动窗口、字符串
2982. 找出出现至少三次的最长特殊子字符串 I	中等	滑动窗口、字符串
76. 最小覆盖子串	困难	滑动窗口、哈希表
438. 找到字符串中所有字母异位词	中等	滑动窗口、哈希表
567. 字符串的排列	中等	滑动窗口、哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/11034463