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.
- 建立一个256位的整型数组来记录所有字符;
- 定义两个变量res和left, res 用来记录最长无重复子串的长度, left 指向该无重复子串左边的起始位置,
- 遍历整个字符串,对于每一个遍历到的字符,如果哈希表中该字符串对应的值为0,说明没有遇到过该字符。则此时计算最长无重复子串,
i - left + 1
。其中i是最长无重复子串最右边的位置,left是最左边的位置。 - 如果该点遇到过,那么更新left的位置。
- 每次循环中,都要把当前字符对应的值赋值为
i + 1
,用于表示当前字符在第几个位置。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256] = { 0 }, res = 0, left = 0;
for (int i = 0; i < s.size(); ++i) {
if (m[s[i]] == 0 || m[s[i]] < left) { //元素虽重复,但是出现在最左边的左边
res = max(res, i - left + 1);
}
else {
left = m[s[i]];
}
m[s[i]] = i + 1;//第几位
}
return res;
}
};
int main() {
Solution test;
cout << test.lengthOfLongestSubstring("abbca");
return 0;
}
本文由 mmmwhy 创作,最后编辑时间为: May 2, 2019 at 01:44 pm