Leetcode 每日一题 3.无重复字符的最长子串
目录
问题描述
输入输出格式
示例
滑动窗口算法步骤
通过图片
代码实现
复杂度分析
题目地址
注意事项
问题描述
给定一个字符串 s，我们需要找出其中不含有重复字符的最长子串的长度。子串是指字符串中连续的字符序列，而子序列则是字符序列，但不必连续。
输入输出格式
- 输入：一个字符串
s。 - 输出：一个整数，表示最长不含有重复字符的子串的长度。
示例
- 输入：
s = "abcabcbb"，输出：3（最长子串为 "abc"）。 - 输入：
s = "bbbbb"，输出：1（最长子串为 "b"）。 - 输入：
s = "pwwkew"，输出：3（最长子串为 "wke"）。
滑动窗口算法步骤
- 初始化：使用一个哈希集合（
HashSet）来存储当前窗口内的字符，两个指针left和right分别表示窗口的左右边界，以及一个变量maxLen来记录最长子串的长度。 - 扩展窗口：移动
right指针向右扩展窗口，直到遇到重复的字符。 - 处理重复：如果遇到重复字符，移动
left指针向右，直到窗口内没有重复字符。 - 更新最长长度：在每次移动
right指针后，更新maxLen，它等于当前窗口的长度，即right - left + 1。 - 返回结果：遍历结束后，
maxLen将包含最长不重复子串的长度。
通过图片
代码实现
java
import java.util.HashSet;
import java.util.Set;
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int maxLen = 0; // 存储最长子串的长度
int left = 0; // 左指针
for (int right = 0; right < s.length(); right++) {
// 如果当前字符已经在窗口中，移动左指针直到窗口内没有重复字符
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
// 将当前字符加入窗口
set.add(s.charAt(right));
// 更新最长子串长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串
s的长度。每个字符最多被访问两次（一次是right指针的移动，一次是left指针的移动）。 - 空间复杂度：O(min(m, n))，其中 m 是字符集的大小。在最坏的情况下，我们需要存储所有字符，这取决于字符集的大小。
题目地址
3. 无重复字符的最长子串 - 力扣（LeetCode）
注意事项
- 确保在移动
left指针时，从set中移除对应的字符。 - 在每次循环中，都更新最长子串的长度，以确保我们得到全局的最长子串。
现实案例分析：文本编辑器中的自动补全
背景
自动补全功能是现代文本编辑器和IDE的标准配置，它能够根据用户的输入提供单词或代码片段的补全建议。这个功能的核心挑战在于如何快速准确地识别出用户可能想要的补全项，同时确保这些建议是唯一的，避免重复。
问题挑战
在代码补全过程中，一个常见的问题是如何处理用户输入的连续代码片段。例如，当用户输入“system.out.println”时，编辑器需要能够识别出这是一个整体的代码片段，而不是将其拆分为“system.out”和“println”两个独立的部分。
解决方案
利用“无重复字符的最长子串”算法，我们可以有效地识别出用户输入中的最长连续无重复字符序列。这可以帮助我们确定最合适的补全建议，从而提供更准确的自动补全功能。