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

算法练习题07：无重复字符的最长子串

news 来源：原创 2024/9/20 7:44:54

我们可以使用 滑动窗口 的方法来解决这个问题。这是一种高效的算法，能在 O(n) 的时间复杂度内完成任务。以下是具体的解题思路：

1. 滑动窗口的概念

滑动窗口的想法是使用两个指针（通常称为左指针 i 和右指针 j）来表示一个窗口。这两个指针在字符串上滑动，以找到满足条件的子串。在这个问题中，我们的目标是找到最长的、没有重复字符的子串。

窗口的定义：窗口是由左指针 i 和右指针 j 所包围的子串 s[i:j]，它包含 i 到 j-1 的字符。

窗口的移动：右指针 j 用于扩展窗口，左指针 i 用于缩小窗口。

2. 使用数据结构来检测重复字符

为了高效地检测一个字符是否已经在当前窗口中，我们使用一个 HashSet 数据结构。HashSet 允许我们在 O(1) 时间复杂度内判断一个字符是否存在，并且可以在 O(1) 时间内添加或移除字符。

3. 具体步骤

初始化：
- 定义一个 HashSet 来存储当前窗口内的字符。
- 初始化两个指针 i 和 j，都指向字符串的开头（即 0）。
- 初始化一个变量 maxLen 来记录最长无重复子串的长度。
遍历字符串：
- 使用 j 遍历整个字符串，将每个字符依次尝试添加到 HashSet 中。
- 如果当前字符 s[j] 不在 HashSet 中：
  - 将其添加到 HashSet 中，表示扩展窗口。
  - 计算当前窗口的长度 j - i + 1，并更新 maxLen。
- 如果当前字符 s[j] 已经存在于 HashSet 中：
  - 说明遇到了重复字符，此时要通过移动左指针 i 来缩小窗口，直到移除重复的字符。
  - 移动左指针的过程中，同时从 HashSet 中移除对应的字符，直到可以将 s[j] 再次安全地添加到 HashSet 中。
更新结果：
- 每次右指针 j 向右移动时，计算当前窗口的长度，并更新 maxLen，以保证 maxLen 始终保持最长无重复子串的长度。
返回结果：
- 当右指针 j 遍历完整个字符串后，maxLen 就是最长无重复子串的长度。

class Solution {public int lengthOfLongestSubstring(String s) {HashSet<Character> set = new HashSet<>();int maxLen = 0;int i = 0, j = 0;int len = s.length();while (j < len) {if (!set.contains(s.charAt(j))) {set.add(s.charAt(j));j++;maxLen = Math.max(maxLen, j - i);} else {// 按顺序移除字符set.remove(s.charAt(i));i++;}}return maxLen;}
}

当右指针 j 遇到一个已经存在于 HashSet 中的字符时，我们需要移动左指针 i，从左侧开始逐个移除字符，直到移除重复的那个字符为止。这样可以确保 HashSet 中的字符总是唯一的。