力扣HOT100-7 无重复字符的最长子串(Java实现)

题目

题目解读

1.必须由原字符串中连续的一段字符组成，不能跳过字符。
2.子串内的任意两个字符都不相同。
3.我们可以选择暴力破解，美剧所有子串并检查每个子串是否有重复字符，但是太慢了。换个思路考虑，拿‘abcdbbacnaxd’举例，无重复字符那么a开始，其子串肯定不能包含a，所以其实区间为'abcdbb'然后再依此判断

开始解题

一、滑动窗口 + HashSet

思路：

用 HashSet 来存储窗口内当前有哪些字符。
加入新字符时，如果 set 中不存在，直接加入并更新长度。
如果 set 中已存在，说明重复，此时需要循环移除左边界字符，直到重复字符被移出窗口为止。

核心流程：

1.初始化 left = 0, max = 0, Set<Character> set = new HashSet<>()。
2.遍历 right 从 0 到 n-1：
取当前字符 c = s.charAt(right)。
当 set 包含 c 时，循环执行：
set.remove(s.charAt(left))。
left++。
将 c 加入 set。
用 right - left + 1 更新 max。
3.返回 max。

代码

public int lengthOfLongestSubstring(String s) { int left = 0, max = 0; Set<Character> set = new HashSet<>(); 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); max = Math.max(max, right - left + 1); } return max; }

二、滑动窗口 + HashMap（跳跃收缩）

思路：

方法一的 while 循环需要一步步移动 left。如果重复字符离 left 很远，比如 "abcdefg...a"，left 要走很多步才能把第一个 a 移除。
我们可以用 HashMap<Character, Integer> 记录每个字符最近一次出现的索引。
当遇到一个已经在 map 中的字符 c 时，我们可以直接将 left 跳到 map.get(c) + 1 的位置，从而一步到位完成收缩。
新的 left 不能比当前 left 小。例如 "abba"，处理到最后一个 a 时，b 的索引可能让我们把 left 跳到很早的位置，这会导致窗口向左回退。因此必须取 Math.max(left, map.get(c) + 1)。

核心流程：

1.初始化 left = 0, max = 0, Map<Character, Integer> map = new HashMap<>()。
2.遍历 right 从 0 到 n-1：
取 c = s.charAt(right)。
如果 map 中包含 c，更新 left = Math.max(left, map.get(c) + 1)。
将 c 的最新索引 right 存入 map。
更新 max = Math.max(max, right - left + 1)。
3.返回 max。

代码

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

感谢您能够看到这里，一起见证小何同学的算法学习，如果您有不同的见解，希望能得到您的指点和点悟；如果您是和我一样的同学，也希望这篇文章能对您有所帮助。