題目
Given a string, find the length of the longest substring without 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 a substring, "pwke" is a subsequence and not a substring.
思路
引子：粗略看了下堂氯，最暴力的方法是分別遍歷頭尾，然后在頭尾間判斷重復(fù)凛篙，時間復(fù)雜度為O(n^4)央拖。
第一種：思考改進(jìn)的方法埂陆，嘗試減少重復(fù)計算敲茄。一開始想的是動態(tài)規(guī)劃射赛，怎么都搞不出來（因為實在也不熟悉動態(tài)規(guī)劃）。后來掃了眼題解论衍，說因為單個子問題可以決定父問題瑞佩，所以可以用貪心。就是在掃描的時候第一個指針不是簡單遞增坯台，而是直接跳過上一個重復(fù)的字母炬丸。這樣可以將時間復(fù)雜度降到O(n^2)。
第二種：再次看題解捂人，發(fā)現(xiàn)可以記錄每個字符上一次出現(xiàn)的位置御雕，這樣就減少了在判斷重復(fù)時的掃描，使時間復(fù)雜度達(dá)到O(n)滥搭。
實現(xiàn)一
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0, j = 0;
int rlt = 0;
while(j < s.length()){
int flag=1;
for(int m=i; m<j ;m++){
if(s[m] == s[j]){
flag = 0;
i = m + 1;
j++;
break;
}
}
if(flag == 1){
if( j-i+1 > rlt){
rlt = j-i+1;
}
j++;
}
}
return rlt;
}
};
實現(xiàn)二
class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int MAX_CHAR = 256;
int pos[MAX_CHAR];
for(int i=0; i<MAX_CHAR; i++){
pos[i] = -1;
}
int i = 0, j = 0;
int rlt = 0;
while(j < s.length()){
if(pos[s[j]] >= i){
i = pos[s[j]] + 1;
}
else{
if( j-i+1 > rlt){
rlt = j-i+1;
}
}
pos[s[j]] = j;
j++;
}
return rlt;
}
};
思考
看了別人的代碼酸纲，發(fā)現(xiàn)有以下可以改進(jìn)
數(shù)組初始化為-1，可以使用
vector<int> last_occ(256, -1);
更方便
