题目
求一个字符串的一个满足要求的最长子字符串，该子字符串不得含有重复的字符，返回该子字符串的长度。
思路
很容易想到一个时间复杂度为O(n^2)的算法。遍历每一个字符，从该字符开始看看以这个字符为起点的最长字符串是多长，最后输出所有字符的最长子字符串长度。
运行时间600ms，击败0%提交
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0;
for(int i=0; i<s.size(); i++){
unordered_set<char> buff;
for(int j=i; j<s.size(); j++){
if(buff.count(s[j]) == 0) buff.insert(s[j]);
else break;
}
if(buff.size() > ret) ret = buff.size();
}
return ret;
}
};
改进
可以看到上面那个算法非常搞笑，是世界上速度最慢的算法。在查找字符串中，我们需要设置一个起点，这个起点是到目前为止，遍历的位置往前最长没有重复出现字符的位置。然后通过与遍历的位置相减，就可以得到最长的子字符串长度了。
运行时间15ms，击败96%提交
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> lastPos(260, -1);
int length = s.size();
int ret = 0;
int start = 0;
for(int i=0; i<length; i++)
{
char c = s[i];
if(lastPos[c]+1 > start) start = lastPos[c] + 1;
if(i-start+1 > ret) ret = i-start+1;
lastPos[c] = i;
}
return ret;
}
};
