每周一道leetcode—— 3. Longest Substring Without Repeating Characters

题目

求一个字符串的一个满足要求的最长子字符串，该子字符串不得含有重复的字符，返回该子字符串的长度。

思路

很容易想到一个时间复杂度为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;
    }
};