LeetCode 剑指 Offer 48. 最长不含重复字符的子字符串

Categories:

题目描述
思路分析
1. 解法一：滑动窗口 + 哈希表（推荐）
相似题目

题目描述

✅ 剑指 Offer 48. 最长不含重复字符的子字符串

思路分析

解法一：滑动窗口 + 哈希表（推荐）

核心思路：

维护一个滑动窗口 [left, right]，保证窗口内无重复字符。

right 向右扩展，用哈希表记录每个字符最近一次出现的下标。

当 s[right] 已在窗口内（即 charIndex[s[right]] >= left），将 left 移动到该字符上次出现位置的下一位，跳过重复字符。

每次更新答案为当前窗口长度 right - left + 1 的最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，每个字符最多被访问两次。

空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 表示字符集大小，最多存储所有不重复字符的下标。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 记录字符最近一次出现的下标
        Map<Character, Integer> charIndex = new HashMap<>();
        int res = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char cur = s.charAt(right);
            // 若当前字符在窗口内出现过，收缩左边界至重复字符的下一位
            if (charIndex.containsKey(cur) && charIndex.get(cur) >= left) {
                left = charIndex.get(cur) + 1;
            }
            // 更新字符最新下标
            charIndex.put(cur, right);
            res = Math.max(res, right - left + 1);
        }

        return res;
    }
}

func lengthOfLongestSubstring(s string) int {
	// 记录字符最近一次出现的下标
	charIndex := map[byte]int{}
	res := 0
	left := 0

	for right := 0; right < len(s); right++ {
		cur := s[right]
		// 若当前字符在窗口内出现过，收缩左边界至重复字符的下一位
		if pre, ok := charIndex[cur]; ok && pre >= left {
			left = pre + 1
		}
		// 更新字符最新下标
		charIndex[cur] = right
		res = max(res, right-left+1)
	}

	return res
}

相似题目

题目	难度	考察点
3. 无重复字符的最长子串	中等	滑动窗口 / 哈希表
159. 至多包含两个不同字符的最长子串	中等	滑动窗口 / 哈希表
340. 至多包含 K 个不同字符的最长子串	中等	滑动窗口 / 哈希表
76. 最小覆盖子串	困难	滑动窗口 / 哈希表
438. 找到字符串中所有字母异位词	中等	滑动窗口 / 哈希表
567. 字符串的排列	中等	滑动窗口 / 哈希表
904. 水果成篮	中等	滑动窗口 / 哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/94004328