題目如下：
Given a string, find the length of thelongest substringwithout repeating characters.
Examples:
Given"abcabcbb", the answer is"abc", which the length is 3.
Given"bbbbb", the answer is"b", with the length of 1.
Given"pwwkew", the answer is"wke", with the length of 3. Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.
分析題目：
首先區(qū)分一個概念： substring與subsequence涯鲁，簡而言之：subsequence可以不是原字符串中連貫的字符（可以略過某些字符），substring必須是原字符串中的一部分
好氛改，下面來看一下題目：
這道題我認為關(guān)鍵在于遇到重復的時候，左面的起始計數(shù)位置怎么跳到之后對應(yīng)的位置误墓，這么說比較抽象甫何，就是從直觀上出發(fā)，我們在左邊有個記錄位置的int型 名為left耕陷，i 就是遍歷變量掂名， left起始為0[string第一個字母下標]，所以遇到的重復情況就是下面幾種哟沫，上圖：
? 由于遇到相同字母饺蔑，此輪計數(shù)結(jié)束，接下來我們要決定left下一步往哪里跳嗜诀，以便于進行下一輪計長度猾警，如圖：
綜上我們可以看出，left的位置取決于重復字母出現(xiàn)的位置隆敢，這時我們就需要一個數(shù)組去記錄字母出現(xiàn)的位置发皿，在這里我使用的是vector<int> asc_table(256, -1)，由于ascii能表示256中字符筑公，我為了left初始化可以與下標相配（即0）雳窟，將所有字母初始位置設(shè)置為-1，再初始化asc_table[s[left]] = 0匣屡，之后就是asc_table[s[i]] = i封救。
由第二幅圖可以看出，當 left <=?asc_table[s[i]] 時捣作，left =?asc_table[s[i]] + 1誉结，并且當前記錄位置的asc_table[s[i]]被更新為最新的、更大一些的i券躁，這樣我們就可以進行下一輪長度計量惩坑。
這是這個思路寫的代碼：
class Solution {public: int lengthOfLongestSubstring(string s) { vector asc_table(256, -1);
? ? ? ? int left = 0;
? ? ? ? int length = 0;
? ? ? ? int temp = 0;
? ? ? ? asc_table[s[left]] = 0;
? ? ? ? if (s.length() == 1) length = 1;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? for (int i = 1; i < s.length(); i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (asc_table[s[i]] == -1)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? asc_table[s[i]] = i;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (left <= asc_table[s[i]]) left = asc_table[s[i]] + 1;
? ? ? ? ? ? ? ? ? ? asc_table[s[i]] = i;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? temp = i - left + 1;
? ? ? ? ? ? ? ? length = (length > temp) ? length : temp;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return length;
? ? }
};
由于? asc_table[s[i]] = i 操作是共通的，所以我合并了一下代碼為：
class Solution {public: int lengthOfLongestSubstring(string s) { vector asc_table(256, -1);
? ? ? ? int left = 0;
? ? ? ? int length = 0;?
? ? ? ? int temp = 0;
? ? ? ? asc_table[s[left]] = 0;
? ? ? ? if (s.length() == 1) length = 1;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? for (int i = 1; i < s.length(); i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (left <= asc_table[s[i]]) left = asc_table[s[i]] + 1;
? ? ? ? ? ? ? ? asc_table[s[i]] = i;
? ? ? ? ? ? ? ? temp = i - left + 1;
? ? ? ? ? ? ? ? length = (length > temp) ? length : temp;
? ? ? ? ? ? }? ? ? ?
? ? ? ? }
? ? return length;
? ? }
};
submit之后通過～這次效率可觀也拜，很開心以舒！雖然寫了很久～這就是今天的積累啦！
