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

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

滑动窗口法解「无重复字符的最长子串」

问题描述

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

示例

输入：s = "abcabcbb"
输出：3（最长子串为 "abc"）

解题思路

滑动窗口法（双指针）

1. 窗口定义：用左右指针 left 和 right 表示当前窗口的左右边界，窗口内字符不重复。

2. 核心操作：
   • 扩展右边界：右指针不断右移，直到遇到重复字符。

   • 收缩左边界：一旦发现重复，左指针右移一位，移除原左边界字符。

3. 去重机制：通过哈希集合 Set 实时记录窗口内的字符，确保窗口的唯一性。

算法流程

步骤详解

1. 初始化：
   • 左指针 left = 0，右指针 right = 0

   • 哈希集合 Set 存储窗口字符

   • 结果变量 res 记录最大长度

2. 滑动窗口扩展：

   for (int left = 0; left < s.length(); left++) {
       // 右指针扩展至出现重复或越界
       while (right < s.length() && !set.contains(s.charAt(right))) {
           set.add(s.charAt(right));
           right++;
       }
       // 更新最大长度
       res = Math.max(res, right - left);
       // 左指针右移一位，移除原左边界字符
       set.remove(s.charAt(left));
   }
   

3. 动态调整：
   • 每次左指针右移后，右指针从当前位置继续扩展，无需回溯。

复杂度分析

• 时间复杂度：O(n)，左右指针各遍历一次字符串。

• 空间复杂度：O(1)，字符集大小固定（ASCII 最多 128 种字符）。

代码实现

public static int lengthOfLongestSubstring(String s) {
    int right = 0;      // 窗口右边界
    int res = 0;        // 最长子串长度
    Set<Character> set = new HashSet<>();

    for (int left = 0; left < s.length(); left++) {
        // 右指针扩展至出现重复或越界
        while (right < s.length() && !set.contains(s.charAt(right))) {
            set.add(s.charAt(right));
            right++;
        }
        // 更新最大长度
        res = Math.max(res, right - left);
        // 左指针右移一位，移除原左边界字符
        set.remove(s.charAt(left));
    }
    return res;
}

力扣通过截图

示例解析

示例 1：s = "abcabcbb"

1. 初始状态：left=0, right=0
   • 窗口扩展至 right=3（字符 a,b,c），此时 res=3

2. 左指针右移：left=1，移除 a
   • 窗口扩展至 right=4（加入 a 失败，窗口变为 b,c,a，res=3

3. 循环结束：最终 res=3

关键点说明
为何时间复杂度是 O(n)？
• 每个字符最多被左右指针各访问一次，无重复操作。

为何用 Set 而不用 Map？
• Set 直接检查是否存在重复，无需记录索引，节省空间。

如何处理中间重复字符？
• 左指针每次仅移动一位，逐步缩小窗口，确保窗口内始终无重复。

拓展思考

优化版本（跳跃式收缩）
若记录字符的最新位置，左指针可跳跃式移动：

Map<Character, Integer> map = new HashMap<>();
int left = 0;
for (int right = 0; right < s.length(); right++) {
    if (map.containsKey(s.charAt(right))) {
        left = Math.max(left, map.get(s.charAt(right)) + 1);
    }
    map.put(s.charAt(right), right);
    res = Math.max(res, right - left + 1);
}

• 优势：减少左指针移动次数，提升效率。

力扣通过截图

通过滑动窗口法，我们高效地解决了子串查重问题，平衡了时间与空间复杂度。此方法在字符串处理中具有广泛的应用场景。