Type：medium
Given a string, find the length of the?longest substring?without repeating characters.
Example 1:
Input: "abcabcbb"Output: 3Explanation:The answer is"abc", with the length of 3.
Example 2:
Input: "bbbbb"Output: 1Explanation: The answer is"b", with the length of 1.
Example 3:
Input: "pwwkew"Output: 3Explanation: The answer is"wke", with the length of 3.? ? ? ? ? ? ? Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.
本題旨在尋找字符串中最長無重復字符子串怎憋。
本題基本解題思路為建立兩個指針i舅列、j削锰，指針i指向無重復的子字符串的第一位葛作，指針j指向最后一位揖铜。在遍歷s的過程中张惹，指針j向前遍歷旺坠，若遇到重復的字符則指針i指向這個重復的字符堂淡，指針j繼續(xù)向后遍歷教馆，直至讀取完整個s字符串逊谋。j、i間的距離就為最長無重復子字符串土铺。
有一個很巧妙的想法胶滋，從ASCII角度考慮板鬓，每一個字符(32-126)都可以轉(zhuǎn)為int型。因此建立一個名叫count的vector<int>型究恤，大小可以為126俭令。建立int型start記錄首字符的位置，賦為初始值-1部宿，maxlen記錄該子字符串長度抄腔，賦為初始值0。首先把所有count值都賦值為-1理张，然后讀取string字符串赫蛇，由于初始化下count[s[i]]均為-1，因此可用來判斷是否之前有重復字符串雾叭。因此在讀取s過程中悟耘，首先判斷count[s[i]]的值是否為-1，若是-1织狐，說明s中該第i位還未重復暂幼，并將count[s[i]]設為i值，即它在s中的位置移迫；若count[s[i]]不為-1旺嬉，說明在這之前已經(jīng)讀取過s[i]，則賦start = count[s[i]]厨埋，即為上一次重復的字符位置邪媳。此時，i - start即為該子字符串的長度揽咕。比較maxlen與該值的大小悲酷，取最大值為新的maxlen。
當i讀取到最后一位亲善，返回maxlen设易，即為所求結(jié)果。
附代碼：
class Solution {
public:
? ? int lengthOfLongestSubstring(string s) {
? ? ? ? int n = s.length();
? ? ? ? int i;
? ? ? ? vector<int> count(128, -1) ;
? ? ? ? int start = -1;
? ? ? ? int maxlen = 0;
? ? ? ? for(i=0; i<n; i++){
? ? ? ? ? ? if(count[s[i]] > start) start = count[s[i]];
? ? ? ? ? ? count[s[i]] = i;
? ? ? ? ? ? maxlen = max(i-start, maxlen);
? ? ? ? }
? ? ? ? return maxlen;
? ? }
};
