longest substring without repeating characters

题目链接: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
using namespace std;

int (string s) {
vector<int> dict(256,-1);
int maxLen = 0, start = -1;
for(int i = 0; i != s.length(); i++) {
if(dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i -start);
}
return maxLen;
}

int main()
{
cout<<length("abcabcbb")<<endl;
}

Output: 3

个人理解
dict 记录当前字符出现的位置
start 记录当前字符出现的上一次位置
参考自https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1737