Medium！
題目描述：給定一個字元串，找出不含有重複字元的 最長子串 的長度。
示例：
給定
"abcabcbb"
"abc"
"bbbbb"
"b"
"pwwkew"
"wke"
"pwke"
是 子序列 而不是子串
解題思路：
這是一道可以跟Two Sum媲美的題。給了我們一個字元串，讓我們求最長的無重複字元的子串，注意這裡是子串，不是子序列，是以必須是連續的。我們先不考慮代碼怎麼實作，如果給一個例子"abcabcbb"，讓你手動找無重複字元的子串，該怎麼找？一個字元一個字元的周遊，比如a，b，c，然後又出現了一個a，那麼此時就應該去掉第一次出現的a，然後繼續往後，又出現了一個b，則應該去掉一次出現的b，以此類推，最終發現最長的長度為3。是以說，我們需要記錄之前出現過的字元，記錄的方式有很多，最常見的是統計字元出現的個數，但是這道題字元出現的位置很重要，是以我們可以使用HashMap來建立字元和其出現位置之間的映射。進一步考慮，由于字元會重複出現，到底是儲存所有出現的位置呢，還是隻記錄一個位置？我們之前手動推導的方法實際上是維護了一個滑動視窗，視窗内的都是沒有重複的字元，我們需要盡可能的擴大視窗的大小。由于視窗在不停向右滑動，是以我們隻關心每個字元最後出現的位置，并建立映射。視窗的右邊界就是目前周遊到的字元的位置，為了求出視窗的大小，我們需要一個變量left來指向滑動視窗的左邊界，這樣，如果目前周遊到的字元從未出現過，那麼直接擴大右邊界，如果之前出現過，那麼就分兩種情況，在或不在滑動視窗内，如果不在滑動視窗内，那麼就沒事，目前字元可以加進來，如果在的話，就需要先在滑動視窗内去掉這個已經出現過的字元了，去掉的方法并不需要将左邊界left一位一位向右周遊查找，由于我們的HashMap已經儲存了該重複字元最後出現的位置，是以直接移動left指針就可以了。我們維護一個結果res，每次用出現過的視窗大小來更新結果res，就可以得到最終結果了。
建立一個256位大小的整型數組來代替哈希表，這樣做的原因是ASCII表共能表示256個字元，是以可以記錄所有字元，然後我們需要定義兩個變量res和left，其中res用來記錄最長無重複子串的長度，left指向該無重複子串左邊的起始位置，然後我們周遊整個字元串，對于每一個周遊到的字元，如果哈希表中該字元串對應的值為0，說明沒有遇到過該字元，則此時計算最長無重複子串，i - left +１，其中ｉ是最長無重複子串最右邊的位置，left是最左邊的位置，還有一種情況也需要計算最長無重複子串，就是當哈希表中的值小于left，這是由于此時出現過重複的字元，left的位置更新了，如果又遇到了新的字元，就要重新計算最長無重複子串。最後每次都要在哈希表中将目前字元對應的值指派為i+1。
C++參考答案一：
1 class Solution {
2 public:
3 int lengthOfLongestSubstring(string s) {
4 int m[256] = {0}, res = 0, left = 0;
5 for (int i = 0; i < s.size(); ++i) {
6 if (m[s[i]] == 0 || m[s[i]] < left) {
7 res = max(res, i - left + 1);
8 } else {
9 left = m[s[i]];
10 }
11 m[s[i]] = i + 1;
12 }
13 return res;
14 }
15 }; 這裡解釋下程式中那個if條件語句中為啥要有個m[s[i]] < left，我們用一個例子來說明，當輸入字元串為"abbca"的時候，當i=4時，也就是即将要開始周遊最後一個字母a時，此時哈希表中a對應1，b對應3，c對應4，left為2，即目前最長的子字元串的左邊界為第二個b的位置，而第一個a已經不在目前最長的字元串的範圍内了，那麼對于i=4這個新進來的a，應該要加入結果中，而此時未被更新的哈希表中a為1，不是0，如果不判斷它和left的關系的話，就無法更新結果，那麼答案就會少一位，是以需要加m[s[i]] < left。
下面這種寫法是上面解法的精簡模式，思路都一樣。
C++參考答案二：
1 class Solution {
2 public:
3 int lengthOfLongestSubstring(string s) {
4 vector<int> m(256, -1);
5 int res = 0, left = -1;
6 for (int i = 0; i < s.size(); ++i) {
7 left = max(left, m[s[i]]);
8 m[s[i]] = i;
9 res = max(res, i - left);
10 }
11 return res;
12 }
13 }; 下面這種解法使用了set，核心算法和上面的很類似，把出現過的字元都放入set中，遇到set中沒有的字元就加入set中并更新結果res，如果遇到重複的，則從左邊開始删字元，直到删到重複的字元停止。
C++參考答案三：
1 class Solution {
2 public:
3 int lengthOfLongestSubstring(string s) {
4 set<char> t;
5 int res = 0, left = 0, right = 0;
6 while (right < s.size()) {
7 if (t.find(s[right]) == t.end()) {
8 t.insert(s[right++]);
9 res = max(res, (int)t.size());
10 } else {
11 t.erase(s[left++]);
12 }
13 }
14 return res;
15 }
16 }; 下面這種解法思路上跟解法一和解法二沒有差別，隻不過使用了HashMap這個資料結構來建立字元和其最後出現位置之間的映射，其他操作均和解法二相同。
C++參考答案四：
1 class Solution {
2 public:
3 int lengthOfLongestSubstring(string s) {
4 int res = 0, left = 0, i = 0, n = s.size();
5 unordered_map<char, int> m;
6 for (int i = 0; i < n; ++i) {
7 left = max(left, m[s[i]]);
8 m[s[i]] = i + 1;
9 res = max(res, i - left + 1);
10 }
11 return res;
12 }
13 }; 知識點回顧：
哈希表
map提供一個很常用的功能，那就是提供key-value的存儲和查找功能。例如，我要記錄一個人名和相應的存儲，而且随時增加，要快速查找和修改。看段代碼：
1 #include <map>
2 #include <string>
3 using namespace std;
4 ...
5 map<string, string> namemap;
6
7 //增加。。。
8 namemap["嶽不群"]="華山派掌門人，人稱君子劍";
9 namemap["張三豐"]="武當掌門人，太極拳創始人";
10 namemap["東方不敗"]="第一高手，葵花寶典";
11 ...
12
13 //查找。。
14 if(namemap.find("嶽不群") != namemap.end()){
15 ...
16 } 這樣做效率很高，100萬條記錄，最多也隻要20次的string.compare的比較，就能找到你要找的記錄;200萬條記錄事，也隻要用21次的比較。
速度永遠都滿足不了現實的需求。如果有100萬條記錄，我需要頻繁進行搜尋時，20次比較也會成為瓶頸，要是能降到一次或者兩次比較是否有可能？而且當記錄數到200萬的時候也是一次或者兩次的比較，是否有可能？而且還需要和map一樣的友善使用。
答案是肯定的。這時你需要has_map. 雖然hash_map目前并沒有納入C++ 标準模闆庫中，但幾乎每個版本的STL都提供了相應的實作。而且應用十分廣泛。在正式使用hash_map之前，先看看hash_map的原理。
1 資料結構：hash_map原理
這是一節讓你深入了解hash_map的介紹，如果你隻是想囫囵吞棗，不想了解其原理，你倒是可以略過這一節，但我還是建議你看看，多了解一些沒有壞處。
hash_map基于hash table（哈希表）。 哈希表最大的優點，就是把資料的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的記憶體。然而在目前可利用記憶體越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。
其基本原理是：使用一個下标範圍比較大的數組來存儲元素。可以設計一個函數（哈希函數，也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下标，hash值）相對應，于是用這個數組單元來存儲這個元素；也可以簡單的了解為，按照關鍵字為每一個元素“分類”，然後将這個元素存儲在相應“類”所對應的地方，稱為桶。
但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，是以極有可能出現對于不同的元素，卻計算出了相同的函數值，這樣就産生了“沖突”，換句話說，就是把不同的元素分在了相同的“類”之中。 總的來說，“直接定址”與“解決沖突”是哈希表的兩大特點。
hash_map，首先配置設定一大片記憶體，形成許多桶。是利用hash函數，對key進行映射到不同區域（桶）進行儲存。其插入過程是：
- 得到key
- 通過hash函數得到hash值
- 得到桶号(一般都為hash值對桶數求模)
- 存放key和value在桶内。
其取值過程是:
- 比較桶的内部元素是否與key相等，若都不相等，則沒有找到。
- 取出相等的記錄的value。
hash_map中直接位址用hash函數生成，解決沖突，用比較函數解決。這裡可以看出，如果每個桶内部隻有一個元素，那麼查找的時候隻有一次比較。當許多桶内沒有值時，許多查詢就會更快了(指查不到的時候).
由此可見，要實作哈希表, 和使用者相關的是：hash函數和比較函數。這兩個參數剛好是我們在使用hash_map時需要指定的參數。
hash_map 使用
2.1 一個簡單執行個體
不要着急如何把"嶽不群"用hash_map表示，我們先看一個簡單的例子：随機給你一個ID号和ID号相應的資訊，ID号的範圍是1～2的31次方。如何快速儲存查找。
1 #include <hash_map>
2 #include <string>
3 using namespace std;
4 int main(){
5 hash_map<int, string> mymap;
6 mymap[9527]="唐伯虎點秋香";
7 mymap[1000000]="百萬富翁的生活";
8 mymap[10000]="白領的工資底線";
9 ...
10 if(mymap.find(10000) != mymap.end()){
11 ...
12 } 夠簡單，和map使用方法一樣。這時你或許會問？hash函數和比較函數呢？不是要指定麼？你說對了，但是在你沒有指定hash函數和比較函數的時候，你會有一個預設的函數，看看hash_map的聲明，你會更加明白。下面是SGI STL的聲明：
1 template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
2 class _EqualKey = equal_to<_Key>,
3 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
4 class hash_map
5 {
6 ...
7 } 也就是說，在上例中，有以下等同關系：
1 ...
2 hash_map<int, string> mymap;
3 //等同于:
4 hash_map<int, string, hash<int>, equal_to<int> > mymap; Alloc我們就不要取關注太多了(希望深入了解Allocator的朋友可以參看标準庫 STL ：Allocator能做什麼)
2.2 hash_map 的hash函數
hash< int>到底是什麼樣子？看看源碼:
1 struct hash<int> {
2 size_t operator()(int __x) const { return __x; }
3 }; 原來是個函數對象。在SGI STL中，提供了以下hash函數：
1 struct hash<char*>
2 struct hash<const char*>
3 struct hash<char>
4 struct hash<unsigned char>
5 struct hash<signed char>
6 struct hash<short>
7 struct hash<unsigned short>
8 struct hash<int>
9 struct hash<unsigned int>
10 struct hash<long>
11 struct hash<unsigned long> 也就是說，如果你的key使用的是以上類型中的一種，你都可以使用預設的hash函數。當然你自己也可以定義自己的hash函數。對于自定義變量，你隻能如此，例如對于string，就必須自定義hash函數。例如：
1 struct str_hash{
2 size_t operator()(const string& str) const
3 {
4 unsigned long __h = 0;
5 for (size_t i = 0 ; i < str.size() ; i ++)
6 __h = 5*__h + str[i];
7 return size_t(__h);
8 }
9 };
10 //如果你希望利用系統定義的字元串hash函數，你可以這樣寫：
11 struct str_hash{
12 size_t operator()(const string& str) const
13 {
14 return __stl_hash_string(str.c_str());
15 }
16 }; 在聲明自己的哈希函數時要注意以下幾點：
- 使用struct，然後重載operator().
- 傳回是size_t
- 參數是你要hash的key的類型。
- 函數是const類型的。
如果這些比較難記，最簡單的方法就是照貓畫虎，找一個函數改改就是了。
現在可以對開頭的"嶽不群"進行哈希化了
. 直接替換成下面的聲明即可：
map<string, string> namemap;
//改為：
hash_map<string, string, str_hash> namemap; 其他用法都不用變。當然不要忘了吧str_hash的聲明以及頭檔案改為hash_map。
官方解答：
方法一：暴力法
直覺
逐個檢查所有的字元串，看它是否不含有重複的字元。
算法
假設我們有一個函數
boolean allUnique(String substring)
，如果子字元串中的字元都是唯一的，它會傳回true，否則會傳回false。 我們可以周遊給定字元串
s
的所有可能的子字元串并調用函數
allUnique
。 如果事實證明傳回值為true，那麼我們将會更新無重複字元子串的最大長度的答案。
現在讓我們填補缺少的部分：
- 為了枚舉給定字元串的所有子字元串，我們需要枚舉它們開始和結束的索引。假設開始和結束的索引分别為 i 和 j。那麼我們有 0≤i<j≤n （這裡的結束索引 j 是按慣例排除的）。是以，使用 i從0到 n - n−1 以及 j 從 i+1到 n這兩個嵌套的循環，我們可以枚舉出
s
- 要檢查一個字元串是否有重複字元，我們可以使用集合。我們周遊字元串中的所有字元，并将它們逐個放入
set
false
true
Java代碼：
1 public class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int n = s.length();
4 int ans = 0;
5 for (int i = 0; i < n; i++)
6 for (int j = i + 1; j <= n; j++)
7 if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
8 return ans;
9 }
10
11 public boolean allUnique(String s, int start, int end) {
12 Set<Character> set = new HashSet<>();
13 for (int i = start; i < end; i++) {
14 Character ch = s.charAt(i);
15 if (set.contains(ch)) return false;
16 set.add(ch);
17 }
18 return true;
19 }
20 } 複雜度分析：
方法二：滑動視窗
暴力法非常簡單。但它太慢了。那麼我們該如何優化它呢？
在暴力法中，我們會反複檢查一個子字元串是否含有有重複的字元，但這是沒有必要的。如果從索引 i 到 j - 1之間的子字元串 sij 已經被檢查為沒有重複字元。我們隻需要檢查 s[j]對應的字元是否已經存在于子字元串 sij 中。
要檢查一個字元是否已經在子字元串中，我們可以檢查整個子字元串，這将産生一個複雜度為 O(n2) 的算法，但我們可以做得更好。
通過使用 HashSet 作為滑動視窗，我們可以用 O(1)的時間來完成對字元是否在目前的子字元串中的檢查。
滑動視窗是數組/字元串問題中常用的抽象概念。 視窗通常是在數組/字元串中由開始和結束索引定義的一系列元素的集合，即 [i, j)（左閉，右開）。而滑動視窗是可以将兩個邊界向某一方向“滑動”的視窗。例如，我們将 [i, j)向右滑動 1 個元素，則它将變為 [i+1,j+1)（左閉，右開）。
回到我們的問題，我們使用 HashSet 将字元存儲在目前視窗 [i,j)（最初 j=i）中。 然後我們向右側滑動索引 j，如果它不在 HashSet 中，我們會繼續滑動 jj。直到 s[j] 已經存在于 HashSet 中。此時，我們找到的沒有重複字元的最長子字元串将會以索引 i 開頭。如果我們對所有的 i 這樣做，就可以得到答案。
1 public class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int n = s.length();
4 Set<Character> set = new HashSet<>();
5 int ans = 0, i = 0, j = 0;
6 while (i < n && j < n) {
7 // try to extend the range [i, j]
8 if (!set.contains(s.charAt(j))){
9 set.add(s.charAt(j++));
10 ans = Math.max(ans, j - i);
11 }
12 else {
13 set.remove(s.charAt(i++));
14 }
15 }
16 return ans;
17 }
18 } 方法三：優化的滑動視窗
Java代碼（使用 HashMap）：
1 public class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int n = s.length(), ans = 0;
4 Map<Character, Integer> map = new HashMap<>(); // current index of character
5 // try to extend the range [i, j]
6 for (int j = 0, i = 0; j < n; j++) {
7 if (map.containsKey(s.charAt(j))) {
8 i = Math.max(map.get(s.charAt(j)), i);
9 }
10 ans = Math.max(ans, j - i + 1);
11 map.put(s.charAt(j), j + 1);
12 }
13 return ans;
14 }
15 } Java代碼（假設字元集為 ASCII 128）：
1 public class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int n = s.length(), ans = 0;
4 int[] index = new int[128]; // current index of character
5 // try to extend the range [i, j]
6 for (int j = 0, i = 0; j < n; j++) {
7 i = Math.max(index[s.charAt(j)], i);
8 ans = Math.max(ans, j - i + 1);
9 index[s.charAt(j)] = j + 1;
10 }
11 return ans;
12 }
13 }