题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
- 0 <= s.length <= 5 * 104
解法
解法一 双指针法
用左指针和右指针之间的空间表示子串。
考虑到要查询字符在子串中是否存在，用查询效率高的HashSet存储出现的字符。
如果在set中已经存在，说明有重复，移动右指针直到没有重复。
直到右指针已经到头为止
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) return s.length(); int left = 0, right = 0;
int maxLength = 0;
Set<Character> set = new HashSet<>();
char[] chars = s.toCharArray();
while (right < chars.length) {
while (set.contains(chars[right])) {
maxLength = Math.max(maxLength, set.size());
set.remove(chars[left]);
left++;
}
set.add(chars[right]);
right++;
}
maxLength = Math.max(maxLength, set.size());
return maxLength;
}
}时间复杂度：O(N)
优化一
注意到提示maxLength = Math.max(maxLength, right-left);
这说明可以用int[128]来对应保存每个字符
直接用这个数组记录每个字符出现的位置Index
- 如果右侧新加入的字符之前的位置在left之后，说明这个字符在窗口中存在，直接移动左边界至这个位置后一位。
- 否则，说明这个字符在窗口中不存在，更新这个字符位置为右指针位置。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) return s.length();
int left = 0, right = 0;
int maxLength = 0;
// charIndex记录字符出现的位置
int[] charIndex = new int[128];
char[] chars = s.toCharArray();
while (right < chars.length) {
char newRightChar = chars[right];
// 右边界新加入的字符在窗口中
while (charIndex[newRightChar] > left) {
maxLength = Math.max(maxLength, right-left);
left = charIndex[newRightChar];
}
// 右边界移动代表有新元素入窗口，在charIndex记录位置
charIndex[newRightChar] = right + 1;
right++;
}
maxLength = Math.max(maxLength, right-left);
return maxLength;
}
}win!!!
解法二 直观解法
用int[108]来记录字符出现次数
- 如果右指针移动后新加入的元素使得这个元素的个数大于1，就移动左指针直到这个cnt重新恢复为1
- 否则就正常移动右指针
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] cnts = new int[108];
char[] chars = s.toCharArray();
int left = 0, right = 0, maxLength = 0;
while(right < chars.length) {
if (++cnts[chars[right] - ' '] > 1) {
while (left < right && cnts[chars[right] - ' '] > 1)
cnts[chars[left++] - ' ']--;
} else {
maxLength = Math.max(maxLength, right - left + 1);
}
right++;
}
return maxLength;
}
}
小结
今天这道题是要找最长子串的长度，首先区分下子串和子序列的区别：
- 子串确实需要元素在原字符串中连续出现。
- 子序列则不要求元素连续，但需要保持原有的顺序。
对于找特定要求的子序列，可以优先考虑一下滑动窗口法，滑动窗口法可以说是双指针的一种变种，左指针表示窗口头，右指针指示窗口尾。具体移动法：
- 通常移动右指针，当右指针不符合条件时（本题是在set中查找到重复元素），移动左指针。
- 直到右指针移动到尾巴结束。
滑动窗口的精髓是在动态移动窗口边界的同时维护一个记录数组。
- 本题是维护字符出现的位置，还可以维护字符的频率、窗口内元素的和、最大/最小值等，每次只更新边界处的元素，省去每次对窗口内部元素的关注。
另外，如果字符串 s 仅由 ASCII 字符组成，可以使用一个 int[128] 数组来存储字符