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.
大致意思:给一个字符串,找到最长子串的长度,要求该子串不包含重复的字符。
常规解法:用哈希表来进行查找,这样查找效率会高些。从字符串头部开始计算子串,将没有重复出现的字符存入哈希表中,如果遇到相同的字符,表明当前不重复子串已经结束,记录此不重复子串的长度,并从哈希表中查到的该重复字符位置开始重新计算子串,比较确定此子串是否是当前最长的,遍历整个字符串后得到不重复字符的最长子串长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> m;
int maxLen = 0;
int start = -1;
for(int i=0; i<s.size(); i++) {
auto it = m.find(s[i]);
if((it != m.end()) && (it->second >= start)) {
start = it->second;
}
m[s[i]] = i;
maxLen = max(maxLen, i-start);
}
return maxLen;
}
};
其他解法:上面用哈希表进行查询虽然相比常规查询要节省时间,但是我们还可以通过更简洁的方法来实现。我们可以用一种更巧妙的方法,因为一个字符占一个字节,八位,字符的ascii范围是在256范围内的,我们可以建立一个256大小的数组,每次字符的查询可以直接通过数组元素地址直接寻址,每一个数组元素的下标就是该字符的ascii值,该数组元素的值是该字符出现在字符串中的位置,每次遍历字符串中的字符,如果没出现重复则元素为默认值,累计字符串长度,如果出现重复则将元素值置为当前字符位置,并且重新计算长度,这样依次遍历完,计算出最长子串长度,时间复杂度会更低。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxlen=0;
int start=-1;
vector<int> vt(256,-1);
for(int i=0;i<s.size();++i)
{
if(vt[s[i]]>start)
{
start=vt[s[i]];
}
vt[s[i]]=i;
maxlen=max(maxlen,i-start);
}
return maxlen;
}
};
网友评论