3.Longest Substring Without Repeating Characters
原题
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.
解决
题目的要求是取最长的不重复子串。一看到是不间断的，就可以想到使用滑动窗口来做。也很明显，这题也可以直接使用暴力解法，枚举后求出最长的不重复子串。
方法1：暴力
public static int lengthOfLongestSubstring(String s) {
//这个暴力解法也还是有很多值得优化的地方O(n^2)
if(s == null || s.length() <= 0 )
return 0;
if (s.length() == 1)
return 1;
int maxLen = 0;
//最外层遍历字符的长度
for(int i = 0; i < s.length() - 1; i++) {
//第二层遍历不重复的最右端
Set<Character> set = new HashSet();
set.add(s.charAt(i));
for(int j = i + 1; j < s.length(); j ++) {
//子串中是否有重复
char c = s.charAt(j);
if(!set.contains(c))
set.add(s.charAt(j));
else {
break;
}
}
maxLen = maxLen > set.size() ? maxLen : set.size();
}
return maxLen;
}
方法2：普通滑动窗口法
public static int lengthOfLongestSubstring(String s) {
//方法2： 使用普通滑动窗口。具体思路：
//一个可变的数组存储不重复的数值。
//R向右边滑动的同时，判断是不是到最右侧。
//每次向右滑动后，判断是否新进入的与之前的有重复，如果重复的话，最左侧--，直到没有重复。
//每次有不重复的子串时，更新全局最大值
if(s == null || s.length() == 0 )
return 0;
int L = 0, R = 0, n = s.length();
Set<Character> window = new HashSet<>();
//因为s肯定不为空，所以maxLen至少也有1
int maxLen = 1;
//保证右侧不越界
while(L < n && R < n) {
if(!window.contains(s.charAt(R))) {
window.add(s.charAt(R ++));
maxLen = maxLen > (R - L) ? maxLen : R - L;
}
else {
window.remove(s.charAt(L ++));
}
}
return maxLen;
}
方法3：优化滑动窗口法
很明显，方法2的普通滑动窗口法是可以优化的，左侧不必每次都减减，而可以直接把窗口内重复的值及其左侧都舍弃掉。
public static int lengthOfLongestSubstring(String s) {
//方法3： 使用优化滑动窗口。具体思路：
//map的key存储不重复的值,value存储位置
//R向右边滑动的同时，判断是不是到最右侧。
//每次向右滑动后，判断是否新进入的与之前的有重复，如果重复的话，最左侧--，直到没有重复。
//每次有不重复的子串时，更新全局最大值
if(s == null || s.length() == 0 )
return 0;
int L = 0, R = 0, n = s.length();
Map<Character, Integer> window = new HashMap<>();
//因为s肯定不为空，所以maxLen至少也有1
int maxLen = 1;
//保证右侧不越界
while(L < n && R < n) {
//当发现重复的字符时,将字符的索引与窗口的左边进行对比，将窗口的左边直接跳到该重复字符的索引处
if (window.containsKey(s.charAt(R))) {
L = window.get(s.charAt(R)) > L ? window.get(s.charAt(R)) : L;
}
maxLen = maxLen > R - L + 1 ? maxLen : R - L + 1;
window.put(s.charAt(R), ++ R);
}
return maxLen;
}