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

Categories:

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

题目描述

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

思路分析

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

核心思路：

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

维护窗口 [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
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口、哈希表
159. 至多包含两个不同字符的最长子串	中等	滑动窗口
340. 至多包含 K 个不同字符的最长子串	中等	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口、哈希表
567. 字符串的排列	中等	滑动窗口、哈希表
424. 替换后的最长重复字符	中等	滑动窗口
904. 水果成篮	中等	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
1695. 删除子数组的最大得分	中等	滑动窗口
2260. 必须拿起的最小连续卡牌数	中等	滑动窗口、哈希表

本文作者: HGNULB

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