3. Longest Substring Without Repeating Characters
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.
这道题求一个字符串的最长不重复子串，思路有三种:
- Brute force:计算每一个子串，然后判断其是否同时满足最长和无重复的条件，这个方法容易想到但一定会造成超时，因为时间复杂度是立方级的。
- hash+sliding window:首先，我们假设目前子串存在于
{i,j}这个区间内，同时我们用哈希表来记录每一个字母的下标，假如此时下标为j+1的元素和前面的区间中某一个字符相同，即存在于哈希表之中，那么我们应该从下标为j+1的元素继续向后搜索，同时从哈希表中删除下标为i的元素;如果这个新的元素不存在于哈希表中，那么只需让j继续向后移动即可，代码如下:
/*solution1 hash-map+sliding window*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty())
return 0;
unordered_map<char,int> hash;
int longest,res=0,i=0,j=0,size=s.size();
string tmp;
while(i<size&&j<size){
if(hash.find(s[j])==hash.end()){
hash[s[j++]]=j;
res=max(res,j-i);
}
else
hash.erase(s[i++]);
}
return res;
}
};
3.array instead of hash:
考虑到题目的特殊性，即样例中只有ASCII码，我们用一个长度为256的数组即可优化时间上的性能，由于我们可以对数组中的元素进行随机访问，所以不用像上面的解法一样进行删除元素的操作，只需要对其左边界调整到下一个位置即可，代码如下：
/*solution2*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> mymap(256,-1);
int i,last=0,res=0;
for(i=0;i<s.length();i++) {
if(mymap[s[i]]==-1 || mymap[s[i]]<last)
res = max(res,i-last+1);
else
last = mymap[s[i]]+1;
mymap[s[i]]=i;
}
return res;
}
};
运行时间从86ms压缩到16ms，时间性能上有了一个巨大的提升。
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。