一、问题背景

在 LeetCode 和各大厂算法面试中，“寻找字符串中最长无重复字符子串”是一道经典高频题。它不仅考察对滑动窗口和哈希表的灵活运用，还能延伸出对时间复杂度优化、边界条件处理的深度思考。本文将通过两种 Java 实现（求长度和求子串本身），结合代码逐行解析

---

二、问题描述

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

---

二、核心思路：滑动窗口如何“丝滑”解决重复问题？

1. 算法思想

• 滑动窗口：用 left 和 right 双指针动态维护一个无重复字符的区间。
• 哈希表：记录字符最后一次出现的索引，实现 O(1) 时间判断重复。

2. 关键操作

• 右指针扩张：遍历字符串，逐个将字符纳入窗口。
• 左指针跳跃：发现重复时，直接跳至重复字符的下一位。
• 实时统计最大值：在窗口滑动过程中动态更新最长子串信息。

---

三、代码实现：逐行解析两种场景

场景1：仅求最长子串长度

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int max = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // 关键！判断重复字符是否在当前窗口内
        if (map.containsKey(c) && map.get(c) >= left) {
            left = map.get(c) + 1; // 左指针跳跃
        }
        map.put(c, right); // 更新字符位置
        max = Math.max(max, right - left + 1); // 实时计算窗口长度
    }
    return max;
}

场景2：输出最长子串本身

public String longestSubstringWithoutRepeating(String s) {
    if (s == null || s.isEmpty()) return "";
    Map<Character, Integer> map = new HashMap<>();
    int maxStart = 0, maxEnd = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c) && map.get(c) >= left) {
            left = map.get(c) + 1;
        }
        map.put(c, right);
        // 记录最长子串的起止位置
        if (right - left > maxEnd - maxStart) {
            maxStart = left;
            maxEnd = right;
        }
    }
    return s.substring(maxStart, maxEnd + 1); // 左闭右开，需+1
}

---

四、面试致命细节：90%候选人会忽略的坑

1. 为什么用 map.get(c) >= left？

• 隐藏坑点：哈希表中记录的字符位置可能是历史值（已不在当前窗口内）。
• 示例：字符串 "abba"，当右指针到最后一个 a 时，map.get('a')=0，但此时左指针已移动到 2，因此不能回退。

2. 如何优化空间复杂度？

• ASCII 场景：若已知字符范围（如仅字母），可用 int[128] 替代哈希表。
• 优化代码：

  int[] index = new int[128]; // ASCII 码范围
  Arrays.fill(index, -1); // 初始化-1表示未出现过
  if (index[c] >= left) { 
      left = index[c] + 1;
  }
  index[c] = right;
  

---

五、LeetCode 实战：测试用例与结果验证

测试用例	预期结果	代码输出
“abcabcbb”	3 (“abc”)	3 (“abc”)
“bbbbb”	1 (“b”)	1 (“b”)
“pwwkew”	3 (“wke”)	3 (“wke”)
“abba”	2 (“ab” 或 “ba”)	2 (“ab”)

---

六、高频面试题：如何让回答让面试官眼前一亮？

Q1：如果字符串长度是 10^6，你的算法还能工作吗？

• 答：可以。算法时间复杂度为 O(n)，空间复杂度 O(m)（m 为字符集大小），均能处理大规模数据。若字符集有限（如 ASCII），空间可视为 O(1)。

Q2：如何证明滑动窗口是最优解法？

• 答：滑动窗口确保每个字符最多被访问两次（进入和离开窗口），时间复杂度严格线性。不存在比 O(n) 更低的理论复杂度，因为必须遍历整个字符串。

Q3：实际工程中哪些场景会用到这个算法？

• 答：
  1. 用户行为分析：检测连续无重复操作序列（如安全审计）。
  2. 数据流去重：实时统计无重复数据段的最大长度。
  3. 生物信息学：DNA 序列中寻找无重复碱基片段。

---

七、总结

本文从算法原理、代码实现到面试考点，全方位解析了“最长无重复子串”问题。掌握滑动窗口与哈希表的配合，不仅能轻松应对 LeetCode，更是提升代码效率的经典思路。