1、题目描述

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

示例 1:

 输入: s = "abcabcbb"
 输出: 3 
 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

 输入: s = "bbbbb"
 输出: 1
 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

 输入: s = "pwwkew"
 输出: 3
 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

2、思路

 第一步：理解题意

关键词：

• 子串（Substring） → 必须是连续的一段字符。

• 无重复字符 → 子串中每个字符只能出现一次。

• 最长 → 我们要找的是满足条件的所有子串中长度最大的那个。

目标：返回这个最大长度。

 第二步：暴力解法（先想笨办法）

我们可以先尝试“暴力枚举所有子串”，然后检查每个子串是否无重复，记录最长的那个。

伪代码：

 for 每个起始位置 i:
     for 每个结束位置 j (j >= i):
         取子串 s[i:j+1]
         检查这个子串是否有重复字符
         如果没有，更新最大长度

//暴力代码
 class Solution {
     public int lengthOfLongestSubstring(String s) {
         int n = s.length();
         int maxLen = 0;
         // 枚举所有起始位置 i
         for (int i = 0; i < n; i++) {
             // 枚举所有结束位置 j（从 i 开始）
             for (int j = i; j < n; j++) {
                 // 检查子串 s[i...j] 是否无重复字符
                 if (isUnique(s, i, j)) {
                     maxLen = Math.max(maxLen, j - i + 1);
                 }
             }
         }
         return maxLen;
     }
     // 辅助函数：判断 s[start...end] 是否无重复字符
     private boolean isUnique(String s, int start, int end) {
         Set<Character> set = new HashSet<>();
         for (int i = start; i <= end; i++) {
             char c = s.charAt(i);
             if (set.contains(c)) {
                 return false; // 发现重复
             }
             set.add(c);
         }
         return true; // 全部不重复
     }
 }

时间复杂度：

• 子串数量：O(n²)

• 检查每个子串是否无重复：O(n)

• 总体：O(n³) → 太慢，不能用于大字符串（比如 n=10⁵）

优点：容易理解

 缺点：效率太低

第三步：优化思路 —— 滑动窗口（Sliding Window）

我们发现：

• 很多子串是重叠的，比如 "abc", "abca"，我们没必要每次都从头检查。

• 如果我们知道当前窗口 [left, right] 是无重复的，那么当 right 向右移动一位，新字符如果重复了，我们只需要移动 left 指针，直到窗口内无重复。

这正是 滑动窗口 的思想！

什么是滑动窗口？

• 用两个指针 left 和 right 表示当前窗口的左右边界。

• right 不断向右扩展窗口。

• 当窗口内出现重复字符时，left 向右收缩窗口，直到没有重复。

• 在每次窗口合法（无重复）时，更新最大长度。

需要用到的 Java 知识点：

1. HashSet：用来快速判断某个字符是否在当前窗口中。

   • add(E e)：添加元素，返回 true 表示添加成功（之前不存在）。

   • contains(Object o)：判断是否包含某元素。

   • remove(Object o)：移除元素。

2. 双指针技巧（Two Pointers）：

   • left 和 right 分别表示窗口左右边界。

   • right 是主循环变量，left 根据条件被动移动。

3. 字符串操作：

   • s.charAt(i)：获取字符串第 i 个字符。

   • 不需要转成 char[]，可以直接用 charAt，节省空间。

第四步：手把手写代码

我们来一步步写：

Step 1：处理边界情况

 if (s == null || s.length() == 0) {
     return 0;
 }

Step 2：初始化变量

 Set<Character> set = new HashSet<>(); // 存储当前窗口中的字符
 int left = 0;                         // 左指针
 int maxLen = 0;                       // 记录最大长度

Step 3：右指针遍历整个字符串

 for (int right = 0; right < s.length(); right++) {
     char c = s.charAt(right);

Step 4：如果当前字符重复，移动左指针直到不重复

    while (set.contains(c)) {
         set.remove(s.charAt(left)); // 移除左边界字符
         left++;                     // 左指针右移
     }

💡 为什么用 while？因为可能要移除多个字符才能让窗口合法。 例如："pwwkew"，当 right 指向第二个 'w' 时，left 要从 0 移动到 2，移除 'p' 和第一个 'w'。

Step 5：把当前字符加入窗口，更新最大长度

     set.add(c);
     maxLen = Math.max(maxLen, right - left + 1);

Step 6：返回结果

 return maxLen;

3、完整代码

import java.util.HashSet;
 import java.util.Set;
 ​
 class Solution {
     public int lengthOfLongestSubstring(String s) {
         if (s == null || s.length() == 0) {
             return 0;
         }
         Set<Character> set = new HashSet<>();
         int left = 0;
         int maxLen = 0;
         for (int right = 0; right < s.length(); right++) {
             char c = s.charAt(right);
             // 收缩窗口，直到没有重复字符
             while (set.contains(c)) {
                 set.remove(s.charAt(left));
                 left++;
             }
             set.add(c); // 扩展窗口
             maxLen = Math.max(maxLen, right - left + 1); // 更新答案
         }
         return maxLen;
     }
 }

时间 & 空间复杂度

• 时间复杂度：O(n) 每个字符最多被 right 访问一次，被 left 移除一次 → 总共 2n 次操作 → O(n)

• 空间复杂度：O(min(m, n)) m 是字符集大小（比如 ASCII 是 128），n 是字符串长度。 set 最多存所有不重复字符 → 最多 min(m, n) 个。

算法思想总结

思想	说明
滑动窗口	用双指针维护一个“合法窗口”，动态调整边界
贪心	每次扩展右边界，尽可能延长合法子串
哈希集合	快速判断字符是否重复，O(1) 时间操作
双指针	left 和 right 协同工作，避免重复计算

思考题

1. 为什么不能只用 if 而必须用 while？----->因为可能要移除多个字符才能消除重复。

2. 能不能不用 Set，用数组代替？----->可以！如果是 ASCII 字符，可以用 boolean[] seen = new boolean[128]，效率更高。

3. 如果要求返回“最长子串”本身，而不仅是长度，怎么改？----->在更新 maxLen 时，同时记录 start 和 end 位置，最后用 substring 截取。