当前位置：首页 > news >正文

【LeetCode 题解】算法：3. 无重复字符最长子串问题

news 2025/3/31 8:56:43

今天，我们继续聚焦于 LeetCode 上一道颇具代表性的题目：给定一个字符串 s ，要求找出其中不含有重复字符的最长子串的长度。这道题不仅考验我们对字符串处理的能力，还需要巧妙的算法思路来高效解决。让我们一步步深入探索，看看如何攻克它。

一、问题深度剖析

题目明确要求从给定的字符串 s 中，找到一个子串，这个子串里所有字符都不重复，并且要使这个子串的长度达到最长，最终返回这个最长子串的长度。这里要特别注意子串和子序列的区别，子串是字符串中连续的一段字符，而子序列中的字符不一定连续。比如在示例 3 中，“pwke” 是子序列，因为它的字符在原字符串中不连续，而 “wke” 才是符合要求的子串。

二、解题思路大揭秘

为了高效解决这个问题，我们可以采用滑动窗口的方法。滑动窗口就像是一个可以在字符串上滑动的 “窗口”，通过动态调整窗口的左右边界，来找到满足条件的最长子串。

具体做法是，使用一个哈希集合（HashSet）来记录当前窗口内出现过的字符。初始时，窗口的左右边界都在字符串的起始位置。然后，不断地将右边界向右移动，每移动一次，就检查新进入窗口的字符是否已经在哈希集合中。如果该字符不在哈希集合中，说明当前窗口内还没有重复字符，将其加入哈希集合，并更新最长子串的长度。如果该字符已经在哈希集合中，那就意味着出现了重复字符，此时需要移动左边界，同时从哈希集合中移除左边界对应的字符，直到窗口内不再有重复字符。

三、示例详解助理解

（一）示例 1：输入 s = "abcabcbb"

初始时，窗口左右边界都在 a 处，哈希集合为空。
右边界右移，加入 a 到哈希集合，当前最长子串长度为 1。
右边界继续右移，加入 b 到哈希集合，最长子串长度更新为 2。
右边界再右移，加入 c 到哈希集合，最长子串长度更新为 3。
右边界移到下一个 a 时，发现 a 已在哈希集合中，此时移动左边界，移除 a，继续移动左边界移除 b，直到移除 c 后，窗口内不再有重复的 a，此时将新的 a 加入哈希集合，窗口继续右移。在这个过程中，最长子串长度保持为 3，最终确定最长子串为 “abc”，长度为 3。

（二）示例 2：输入 s = "bbbbb"

窗口从第一个 b 开始，加入 b 到哈希集合，最长子串长度为 1。
右边界每次右移，遇到的都是已在哈希集合中的 b，不断移动左边界，但由于整个字符串都是 b，最长子串始终是单个 b，长度为 1。

（三）示例 3：输入 s = "pwwkew"

窗口从 p 开始，加入 p 到哈希集合，最长子串长度为 1。
右移加入 w，长度更新为 2。
再右移遇到重复的 w，移动左边界移除 p，但 w 仍重复，继续移动左边界，直到移除第一个 w，加入新的 w，此时窗口内无重复字符，继续右移。
加入 k 和 e，最长子串长度更新为 3，确定最长子串为 “wke”，长度为 3。

四、Java 代码实现展示

public class LongestSubstringWithoutRepeatingChars {public int lengthOfLongestSubstring(String s) {// 用于存储已经出现过的字符Set<Character> charSet = new HashSet<>();int maxLength = 0;int left = 0;int right = 0;while (right < s.length()) {if (!charSet.contains(s.charAt(right))) {// 如果当前字符不在集合中，将其加入集合charSet.add(s.charAt(right));// 更新最长子串长度maxLength = Math.max(maxLength, right - left + 1);right++;} else {// 如果当前字符在集合中，移动左边界并移除左边界的字符charSet.remove(s.charAt(left));left++;}}return maxLength;}public static void main(String[] args) {LongestSubstringWithoutRepeatingChars solution = new LongestSubstringWithoutRepeatingChars();String s1 = "abcabcbb";System.out.println(solution.lengthOfLongestSubstring(s1));String s2 = "bbbbb";System.out.println(solution.lengthOfLongestSubstring(s2));String s3 = "pwwkew";System.out.println(solution.lengthOfLongestSubstring(s3));}}

五、代码逐行解读

（一）初始化部分

创建一个 HashSet 集合 charSet 用于存储已经出现过的字符。
初始化 maxLength 为 0，用于记录最长子串的长度。
left 和 right 分别表示滑动窗口的左右边界，初始都为 0。

（二）循环部分

while 循环条件为 right < s.length()，只要右边界没有超出字符串长度就继续循环。
检查当前右边界字符 s.charAt(right) 是否在 charSet 中，如果不在，将其加入集合，更新 maxLength 为当前窗口长度（right - left + 1），然后右边界右移。
如果当前右边界字符在 charSet 中，说明出现重复字符，移除左边界字符 s.charAt(left)，并将左边界左移。