赞
踩
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解决这个问题的关键在于使用滑动窗口和哈希集来维护一个当前不含重复字符的子串。
详细解释解题思路:
left
和right
来表示滑动窗口的左右边界,初始时都指向字符串的开头。right
指针向右移动,逐个将字符加入哈希集中,同时检查是否出现了重复字符。如果出现了重复字符,说明当前子串中不再是不含重复字符的子串,需要调整窗口的左边界。具体步骤如下:
right
指针向右移动一位。left
指针向右移动一位,直到当前窗口中不再有重复字符。right
指针时,都要记录当前窗口的大小,并用一个变量maxLen
来维护记录最大的窗口大小。right
指针到达字符串的末尾,整个过程中不断更新maxLen
,最终maxLen
的值就是不含重复字符的最长子串的长度。maxLen
作为答案。这个算法的关键在于通过滑动窗口的方式,动态地调整窗口的大小,以保持窗口内的字符都不重复,并且在遍历过程中不断更新最大子串的长度。这样可以在一次遍历中解决问题,而不需要额外的循环来检查所有可能的子串。时间复杂度为O(n),其中n是字符串的长度。
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxLen = 0; int left = 0; int right = 0; HashSet<Character> set = new HashSet<>(); while (right < n) { if (!set.contains(s.charAt(right))) { set.add(s.charAt(right)); right++; maxLen = Math.max(maxLen, set.size()); } else { set.remove(s.charAt(left)); left++; } } return maxLen; } }
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int maxLen = 0; int[] charIndex = new int[256]; // 使用数组代替哈希集 Arrays.fill(charIndex, -1); // 初始化数组为-1 int left = 0; for (int right = 0; right < n; right++) { char c = s.charAt(right); if (charIndex[c] != -1) { left = Math.max(left, charIndex[c] + 1); // 直接将左边界移到重复字符的下一个位置 } charIndex[c] = right; maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。