前端宝藏知识
第三题： 无重复字符的最长子串
 
难度：中等
 
题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。 
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 
题目解答：
要解决这个问题，我们可以使用滑动窗口（双指针）的方法来找出最长的不含重复字符的子串。
解题思路：
1. 使用哈希集合来存储字符： 我们可以使用一个哈希集合（或者字符数组）来存储当前窗口内的字符，以及它们出现的次数。
2. 滑动窗口： 使用两个指针 left 和 right 表示当前窗口的左右边界。开始时，两个指针都位于字符串的开头。
3. 扩展右边界： 右指针不断向右移动，每次移动时将右边界的字符加入哈希集合中。如果发现当前字符已经在集合中存在（即重复），则需要收缩左边界，直到窗口内不再有重复字符。
4. 计算窗口长度： 每次右指针移动时，都更新最大子串长度。
5. 复杂度优化： 使用哈希集合可以快速判断字符是否重复，使得每个字符最多被访问两次（一次加入集合，一次从集合中移除），时间复杂度为 O(n)。
 
JavaScript 实现：
解释：
• set 用于存储当前窗口内的字符。
• left 和 right 分别代表当前窗口的左右边界。
• 当 right 指向的字符不在集合中时，将其加入集合并更新最大长度；否则，移动 left 指针直到重复字符被移除。
• 每次迭代都会更新 maxLen，最终返回的即为最长不含重复字符的子串长度。这种方法保证了每个字符只被访问一次，因此是高效的解决方案。
 
 
 
 
2024-07-08
浏览97
力扣算法题
登录后评论
评论
分享