leetcode刷题（3）——无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
解题思路： 这道题主要用到思路是：滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
刚开始的想法1: 刚开始想的是判断队列的首和尾是否和即将进来的元素有一致的，如果是首是一致的，就移除首，尾部一致，就将整个队列移除干净，于是有了如下的写法：
class Solution {
public int lengthOfLongestSubstring(String s) {
ArrayDeque<Character> arrayDeque = new ArrayDeque<>();
int maxSize = 0;
for(int i=0;i<s.length();i++){
Character charSet = s.charAt(i);
if(arrayDeque.isEmpty()){
arrayDeque.add(charSet);
}else{
Character firstChar = arrayDeque.peek();
Character lastChar = arrayDeque.getLast();
if(firstChar!=null&&firstChar.equals(charSet)){
arrayDeque.poll();
}else if(lastChar!=null&&lastChar.equals(charSet)){
while(!arrayDeque.isEmpty()){
arrayDeque.poll();
}
}
arrayDeque.add(charSet);
}
maxSize = Math.max(maxSize,arrayDeque.size());
}
return maxSize;
}
}这个直接就错了，如果输入是"abcabcbb"，我的写法输出4，正确结果是3，原因是没有考虑中间元素也可能和即将进来的元素会重合。
错误想法2: 决定用left和right来记录滑动窗口的左右边界，于是写了如下写法：
class Solution {
public int lengthOfLongestSubstring(String s) {
int left =0;
int right=0;
int max = 0;
HashMap<Character,Integer> map = new HashMap();
for(int i=0;i<s.length();i++){
Character charDex = s.charAt(i);
if(!map.containsKey(charDex)){
map.put(charDex,i);
}else{
int index = map.get(charDex);
left = i;
map.put(charDex,i);
}
right = i;
max = Math.max(right-left+1,max);
}
return max;
}
}问题就是出在了left的更新上，这里left = i;的话，“dvdf"系统输出3，我输出2，如果是left=index+1;输入"abba”，系统输出2，我输出3, 所以左界限应该定义为 left = Math.max(left,index+1);，这里这个题目唯一难点
通用模版：
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
int left = 0;
for(int i = 0; i < s.length(); i ++){
if(map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-left+1);
}
return max;
}
}耗时解法1：
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray();
String pre = "";
int index;
int max = 0;
LinkedHashMap<Character, Integer> linkedHashMap = new LinkedHashMap<>();
ArrayDeque<Character> arrayDeque = new ArrayDeque<>();
for (index = 0; index < chars.length; index++) {
char charDex = chars[index];
if (linkedHashMap.containsKey(charDex)) {
int indexRepeat = linkedHashMap.get(charDex);
for (Map.Entry<Character, Integer> entry : linkedHashMap.entrySet()) {
int value = entry.getValue();
Character key = entry.getKey();
if (value <= indexRepeat) {
// linkedHashMap.remove(key);
arrayDeque.push(key);
}
}
}
while (arrayDeque.size() != 0) {
Character character = arrayDeque.poll();
linkedHashMap.remove(character);
}
linkedHashMap.put(charDex, index);
max = Math.max(max, linkedHashMap.size());
}
return max;
}这个是我最初的解法，实在太耗时了，于是优化了一下：
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}解法3:使用滑动窗口的模版 **注意：**之前滑动窗口的模版可以使用数组来作为 窗口，但是在这个问题上就能不使用了，因为这里没有说字符串只由26个字母组成，所以可能出现“ ”的字符串，必须使用map
class Solution {
public int lengthOfLongestSubstring(String s) {
int left =0;
int right=0;
int max = 0;
HashMap<Character,Integer> window = new HashMap();
while(right<s.length()){
char charDex = s.charAt(right);
right++;
window.put(charDex,window.getOrDefault(charDex,0)+1);
while(window.getOrDefault(charDex,0)>1){
char leftChar = s.charAt(left);
window.put(leftChar,window.getOrDefault(leftChar,0)-1);
left++;
}
max = Math.max(right-left,max);
}
return max;
}
}注意：这里的 max = Math.max(right-left,max);是放在while(right<s.length())这个循环中，因为要缩短了左边界，窗口长度固定以后，才开始比较大小
腾讯云开发者
