题目
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
相关标签
哈希表 双指针 字符串 滑动窗口
解法思路
- 既然是让求没有重复元素的最大子串，于是想到用滑动窗口在给定字符串 s 中“向右滑动”的过程中，将新纳入滑动窗口的字符丢入一个集合；
- 用一个变量
lengthRecord记录出现的无重复子串的最长长度； - 如果每次纳入滑动窗口的新字符都能成功的丢入这个集合，那么记录
lengthRecord就会不断被打破； - 如果纳入滑动窗口的新字符无法被丢入滑动窗口，说明滑动窗口中已经存在这个字符，那么就要缩短滑动窗口到与新字符重复的字符的右边，此时记录
lengthRecord不因滑动窗口纳入新的字符而被打破，于是继续“向右滑动”窗口，期待以后的某一时刻，当有新字符纳入滑动窗口时，会打破记录lengthRecord；
解法实现（一）
- 滑动窗口的边界用变量
l和r表示，滑动窗口中的字符用集合windowSet盛接；
关键词
滑动窗口 双指针 字符串
package leetcode._3;
import java.util.HashSet;
import java.util.Set;
public class Solution {
public int lengthOfLongestSubstring(String s) {
int l = 0, r = -1;
int lengthRecord = 0;
Set<Character> windowSet = new HashSet<>(s.length());
while (l < s.length() && r + 1 < s.length()) {
r++;
char c = s.charAt(r);
boolean isAdded = windowSet.add(c);
if (!isAdded) {
while (s.charAt(l) != c && l + 1 < s.length()) {
windowSet.remove(s.charAt(l));
l++;
}
windowSet.remove(s.charAt(l));
l++;
windowSet.add(c);
}
lengthRecord = Math.max(lengthRecord, windowSet.size());
}
return lengthRecord;
}
public static void main(String[] args) {
int result = (new Solution()).lengthOfLongestSubstring("abcabcbb");
System.out.println(result);
}
}
解法实现（二）
- 对于字符串来说，每个字母 char 其实就是 int，而且英文总共 26 个字母，所以可以用一个 int 型数组作为字母频次的统计，每个字母对应的 ASCII 码就是数组的索引 ；
- 相比于向集合中添加字母从而保证不出现重复的字母而言，用数组统计字母的频次的时间复杂度是 O(1)，快于集合的 O(logN)；
-
res还是一个一旦被撑大就无法缩小的窗口，用来记录出现的最长的无重复子串的长度；
关键词
字母的 ASCII 码对应数组的索引
// 滑动窗口
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
class Solution1 {
public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
// 整个循环从 l == 0; r == -1 这个空窗口开始
// 到l == s.size(); r == s.size()-1 这个空窗口截止
// 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
while(l < s.length()){
if(r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
freq[s.charAt(++r)] ++;
else //r已经到头 || freq[s[r+1]] == 1
freq[s.charAt(l++)] --;
res = Math.max(res, r-l+1);
}
return res;
}
}
