题目链接： 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)，如果子字符串中的字符都是唯一的，则返回true，否则返回false。我们可以遍历给定字符串s的所有可能的子字符串，并调用函数allUnique。如果它被证明是正确的，那么我们更新子字符串的最大长度的答案，不需要重复字符。
public 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