1. 題目
給定一個字符串，找出其中不含重復(fù)字符的最長子串的長度。
示例1：
輸入："abcabcbb"
輸出：3
解釋：因為無重復(fù)字符的最長子串是："abc"谭跨，所以其長度為3
示例2：
輸入："bbbbb"
輸出：1
解釋：因為無重復(fù)字符的最長子串是："b"，所以其長度為1
示例3：
輸入："pwwkew"
輸出：3
解釋：因為無重復(fù)字符的最長子串是："wke"或"kew"，所以其長度為3
注意：必須是子串的長度囚灼，子串是連續(xù)的字符，中間不能跳躍字符祭衩，如"pwke"是一個子系列灶体，不是子串。
2. 解題思路
2.1 思路一：滑動窗口
窗口通常是在數(shù)組/字符串中由開始和結(jié)束索引定義的一系列元素的集合掐暮，即[i, j)（左閉蝎抽，右開），而滑動窗口是可以將兩個邊界向某一方向“滑動”的窗口路克。
例如：
我們將[i, j)向右滑動1個元素樟结，則它將變?yōu)?code>[i+1, j+1)（左閉，右開）
用HashSet存儲當前處于窗口[i, j)(最初 j = i)中的字符精算，然后我們向右滑動索引j瓢宦，如果它不在HashSet中，我們會繼續(xù)滑動j灰羽，直到s[j]已經(jīng)存在于HashSet中驮履，此時沒有重復(fù)的最長子字符串將會以索引i開頭
用
HashSet存放當前處于滑動窗口中的字符，初始HashSet為空廉嚼。
窗口的左邊i不動玫镐，右邊j向右滑動，依次遍歷字符：j為指向字符的索引怠噪。
當j = 0時恐似，遍歷字符p，加入HashSet -- [p]舰绘，則目前無重復(fù)字符的最大子串長度maxSubLength = 1
當j = 1時蹂喻，遍歷字符w葱椭，加入HashSet -- [p, w]，則maxSubLength = 2滑動窗口1.png當j = 2時口四，遍歷字符w孵运，此時HashSet中已包含重復(fù)字符w，
則窗口的左邊i向右滑蔓彩，右邊j不動治笨，HashSet依次刪除索引i所指向的字符，直到HashSet不再包含該字符w赤嚼，
然后重新將遍歷字符w加入HashSet中旷赖，啟動窗口j繼續(xù)右滑。滑動窗口2.png窗口的左邊
i不動更卒，右邊j繼續(xù)向右滑動等孵，依次遍歷字符：j為指向字符的索引
當j = 3時，遍歷字符k蹂空，加入HashSet -- [w k]
當j = 4時俯萌，遍歷字符e，加入HashSet -- [w k e]上枕，則此時maxSubLength = 3
滑動窗口3.png當j = 5時咐熙，遍歷字符w，此時HashSet中已包含重復(fù)字符w辨萍，
則窗口的左邊i向右滑棋恼，右邊j不動，HashSet依次刪除索引i所指向的字符锈玉，直到HashSet不再包含該字符w爪飘，
然后重新將遍歷字符w加入HashSet中，啟動窗口j右滑嘲玫。
結(jié)束悦施，則maxSubLength = 3滑動窗口4.png
代碼實現(xiàn)：
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int n = s.length();
Set<Character> set = new HashSet<>();
int maxLength = 0;
int i = 0;
int j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
maxLength = Math.max(j - i, maxLength);
} else {
set.remove(s.charAt(i++));
}
}
return maxLength;
}
2.2 思路二：優(yōu)化的滑動窗口
針對上述的滑動窗口方法，不使用集合來判斷一個字符是否存在去团，而定義字符到索引的映射map抡诞。
當找到重復(fù)字符時，可以立即跳過該窗口土陪。
如果在[i, j)范圍內(nèi)有與s[j]重復(fù)的字符昼汗，索引為j'，即[i, ... j', ... j)鬼雀，
我們不需要逐漸增加i顷窒，可以直接跳過[i, j']范圍內(nèi)的所有元素，并將i變?yōu)?code>j' + 1
舉例：
s = "pwwkew"，當 j = 2時鞋吉，窗口[0, 2)范圍內(nèi)有與s[2]重復(fù)的字符w鸦做，索引為1(j' = 1)，我們可以直接跳過[0, 1]范圍內(nèi)的所有元素谓着，將i變?yōu)?(j' + 1)
代碼實現(xiàn)：
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int n = s.length();
Map<Character, Integer> map = new HashMap<>(16);
int maxLength = 0;
for (int i = 0,j = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
maxLength = Math.max(maxLength, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return maxLength;
}
2.3 思路三：使用列表List存儲不重復(fù)字符
依次遍歷字符串 s 中的每次字符泼诱，若不是重復(fù)字符，加入一個列表list中赊锚，若是重復(fù)字符治筒，則刪除列表list中該重復(fù)字符以及前面的所有字符，然后再將該重復(fù)字符加入此列表list中舷蒲。
在遍歷的過程中統(tǒng)計出列表list中存儲的最大字符個數(shù)耸袜，即為字符串 s 中不含重復(fù)字符的最長子串的長度。
代碼實現(xiàn)
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
List<Character> list = new ArrayList<>();
int n = s.length();
int maxLength = 0;
for (int i = 0; i < n; i++) {
int index = list.indexOf(s.charAt(i));
if (index == -1) {
list.add(s.charAt(i));
maxLength = Math.max(list.size(), maxLength);
} else {
for (int j = index; j >= 0; j--) {
list.remove(j);
}
list.add(s.charAt(i));
}
}
return maxLength;
}
