目录
无重复字符的最长子串问题详解与解决方法1. 介绍问题描述示例2. 解题思路3. 算法实现4. 复杂度分析5. 测试与验证6. 总结7. 参考文献
感谢阅读！
无重复字符的最长子串问题详解与解决方法
1. 介绍
无重复字符的最长子串问题是 LeetCode 经典题目之一，要求找出一个给定字符串中不含有重复字符的最长子串的长度。
问题描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。
2. 解题思路
使用滑动窗口（双指针）和哈希集合的方法解决该问题：
使用两个指针 left 和 right 表示滑动窗口的左右边界，初始都指向字符串的开头。使用哈希集合 set 存储当前窗口内的字符，初始为空。遍历字符串 s，右指针 right 不断向右移动，将字符加入 set 中，直到遇到重复字符。如果遇到重复字符，则左指针 left 向右移动，直到将重复字符移出窗口，同时从 set 中移除这些字符。在遍历过程中，不断更新最长子串的长度。
3. 算法实现
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set
int maxLength = 0, left = 0, right = 0;
while (right < n) {
char ch = s.charAt(right);
while (set.contains(ch)) {
set.remove(s.charAt(left));
left++;
}
set.add(ch);
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
4. 复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。两个指针 left 和 right 各遍历一次字符串。空间复杂度：O(min(m, n))，其中 m 是字符集的大小（假设为常数，比如英文字母），n 是字符串 s 的长度。哈希集合 set 最多存储字符集的大小个元素。
5. 测试与验证
设计不同测试用例，包括空字符串、全重复字符、无重复字符等情况，验证算法的正确性和效率。
6. 总结
无重复字符的最长子串问题是一个经典的滑动窗口应用问题。通过本文的详细讲解和算法实现，可以有效地解决该问题，找出字符串中不含重复字符的最长子串的长度。
7. 参考文献
LeetCode 官方网站《算法导论》《程序员面试金典》
感谢阅读！
推荐文章
发表评论