Leetcode 3. Longest Substring Without Repeating Characters 题解

最后编辑于: 2016-03-30

我的解

很直接的思路，遇到重复的就删到该字符，更新length。 42ms

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.size())
            return 0;
        std::vector<char> char_vec;
        char_vec.push_back(s[0]);
        unsigned int length = 1;
        unsigned int max_len = length;
        for (size_t i = 1; i < s.size(); ++i)
        {
            if (std::find(char_vec.begin(), char_vec.end(), s[i])==char_vec.end())
            {
                length++;
                max_len = length > max_len? length:max_len;
            }
            else
            {
                while(char_vec[0] != s[i])
                    char_vec.erase(char_vec.begin());
                char_vec.erase(char_vec.begin());
                length = char_vec.size()+1;
            }
            char_vec.push_back(s[i]);
        }
        return max_len;
    }
};

更好的解

维护一个 hash 表，Key 为s[i]，Value 为其在s中的位置。设置一个 start 标记当前子串的起点。若重复字符出现，更新ans和start，并且保证每次读入一个字符都更新 hash 表。

16 ms

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[256];
        memset(hash, -1, sizeof(hash));
        int start = 0, ans = 0;
        int i;
        for(i = 0; i < s.size(); i++){
            if( -1 != hash[s[i]] ){
                if(ans < i - start)
                    ans = i - start;
                if(hash[s[i]] + 1  > start )
                    start = hash[s[i]] + 1;
            }
            hash[s[i]] = i;
        }
        if(ans < i - start)
            ans = i - start;
        return ans;
    }
    };

启发

使用类似于 start 这样的标记，可以避免对数据的实际操作（如我的解中的push_back和erase操作），从而节省时间。