题目链接： https://leetcode.com/problems/longest-substring-without-repeating-characters/
1. 题目介绍（最长无重复字符的子串）
Given a string s, find the length of the longest substring without repeating characters.
【Translate】： 给定一个字符串s，找出不重复字符的最长子字符串的长度。
测试用例：
【Key】： 注意，答案必须是子字符串，“pwke”是子序列而不是子字符串。
约束：
2. 题解
2.1 错误示范 - 双端队列
一开始没读懂题，怎么就abc就是最小字符串了，明明abc重复了啊，后来才理解，这个最小字符串要求的是这个子字符串中没有重复的字符。下面的代码并没有成功AC，拿出来当个反面教材。这个一开始的想法是想通过双端队列，来判断队列中前后重复的元素，然后遇到重复元素后，将从一开始记录到现在的count数存入hashMap中，最后通过遍历hashMap找最大的方式得到最后的答案。感觉想法是挺好的，但是现实却不是这样的，这个题它不单单是前后两端的问题，同时还要求了中间的元素也不能重复，所以这个方法就出现了致命性的问题。
class Solution {public int lengthOfLongestSubstring(String s) {Deque<Character> queue = new LinkedList<>();// Queue<Character> queue = new LinkedList<>();char tmp = ' ';int count = 0;int j = 0;HashMap<Integer,Integer> map = new HashMap<>();for(int i = 0; i < s.length(); i++){tmp = s.charAt(i);if(queue.isEmpty() && j == 0){queue.offer(tmp);count++;j++;}else if (queue.isEmpty() && j != 0){queue.offer(tmp);System.out.println(tmp);map.put(j,count);j++;count = 1;}else if(queue.peekFirst() == tmp){queue.poll();// System.out.println(tmp);// System.out.println(i);}else if(queue.peekLast() == tmp){queue.clear();queue.offer(tmp);count = 1;}else{queue.offer(tmp);System.out.println(tmp);count++;}if(i == s.length()-1){map.put(j,count); }}int max = 0;for(int i = 1; i <= map.size(); i++){// System.out.println(map.get(i));if(map.get(i) > max){max = map.get(i);}}return max;}
}
2.2 暴力枚举【Solution】O(n^3)
boolean allUnique(String substring)allUniquepublic class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length();int res = 0;for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {if (checkRepetition(s, i, j)) {res = Math.max(res, j - i + 1);}}}return res;}private boolean checkRepetition(String s, int start, int end) {int[] chars = new int[128];for (int i = start; i <= end; i++) {char c = s.charAt(i);chars[c]++;if (chars[c] > 1) {return false;}}return true;}
}
2.3 滑动窗口【Solution】O(n)
不得不佩服！滑动窗口的方案是通过两个下标【left】和【right】控制窗口的大小（即，子字符串的大小）。当右边界下标指到的位置出现重复，就开始移动左边界下标，直到移动到重复字符的位置+1。
public class Solution {public int lengthOfLongestSubstring(String s) {int[] chars = new int[128];int left = 0;int right = 0;int res = 0;while (right < s.length()) {char r = s.charAt(right);chars[r]++;while (chars[r] > 1) {char l = s.charAt(left);chars[l]--;left++;}res = Math.max(res, right - left + 1);right++;}return res;}
}
2.4 滑动窗口优化 O(n)
2.3方案最多需要 2n 个步骤。事实上，它可以被优化为只需要 n 个步骤。我们可以定义字符到其索引的映射，而不是使用集合来判断字符是否存在。然后我们可以在发现重复字符时立即跳过字符。但是不知道为什么优化了反而变慢了 ？？？
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. 可参考
[1] Java判断Stack和Queue是否为空的方法
[2] Java HashMap
[3] 学习笔记 | Java的队列Queue、PriorityQueue、Deque