Code Bye

Leetcode提交代码Time Limit Exceeded

在Leetcode上面提交代码(第三题:Longest Substring Without Repeating Characters),提示Time Limit Exceeded。本人在VS上面可以正常运行,对于Leetcode的测试例子,运行时间大约是100ms。
本人的代码如下:
//暴力搜寻,从头到尾遍历子串
class Solution {
public:
/   int lengthOfLongestSubstring(string s) {
int max = 0;
string str;
for (int index_x = s.size(); index_x >= 0; –index_x)
{
for (int index_y = 0; index_y < index_x; ++index_y)
{
str=s.substr(index_y, index_x-index_y);
if (str.size() <= max)
{
break;
}
//对子串先排序,再删除重复,假如没有重复就判定替换最大长度
sort(str.begin(), str.end());
if (unique(str.begin(), str.end()) == str.end())
{
if (str.size() > max)
{
max = str.size();
break;
}
}
}
}
return max;
}
};
//本人实现查询重复函数,但效率没有上面的高
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max = 0;
string str;
for (int index_x = s.size(); index_x >= 0; –index_x)
{
for (int index_y = 0; index_y < index_x; ++index_y)
{
str=s.substr(index_y, index_x-index_y);
if (str.size() <= max)
{
break;
}
if (unique_str(str))
{
if (str.size() > max)
{
max = str.size();
break;
}
}
}
}
return max;
}
bool unique_str(string str_u)
{
bool flag;
set<char> set_str;
for (int i = 0; i < str_u.size(); ++i)
{
if (set_str.count(str_u.at(i)))
{
flag = false;
break;
}
else
{
flag = true;
}
set_str.insert(str_u.at(i));
}
return flag;
}
};
解决方案

30

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) {
            return 0;
        }
        auto max = 0;
        auto begin = 0;
        auto end = 0;
        int m[129] = {};
        for (auto i = 0; i < 129; ++i) {
            m[i] = -1;
        }
        auto length = 0;
        while (begin < (int)s.size() && end < (int)s.size()) {
            if (m[s[end]] < begin) {
                ++length;
            } else {
                if (length > max) {
                    max = length;
                }
                begin = m[s[end]] + 1;
                length = end - begin + 1;
            }
            m[s[end]] = end;
            ++end;
        }
        if (length > max) {
            max = length;
        }
        return max;
    }
};

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Leetcode提交代码Time Limit Exceeded