LEETCODE，leetcode--Longest Substring Without Repeating Characters

2023-10-27 阅读 32 评论 0

摘要：1.題目描述 Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest

1.題目描述

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

2.解法分析

要找出最長的字符不重復的字串,由不重復二字很容易讓人想到hash表,所以我的思路很自然就到unordered_set上面了，對于字符串的題目，很明顯需要遍歷字符串，遍歷過程中設置一個變量隨時記錄當前得到字符不重復的最長字符的長度，然后設置一個變量記錄以當前字符為結束字符的最長字符不重復的子串的長度，這樣一定遇到重復的話可以立馬根據這個變量回搜。代碼如下：

class Solution {

public:

    int lengthOfLongestSubstring(string s) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if(s.length()<=1)return s.length();

        unordered_set<char> myHash;

        int LongestLen=0;

        int curLen=0;

        for(int i=0;i<s.length();++i)

            if(myHash.count(s[i])==1)

                for(int j=i-curLen;j<i;++j)

                    if(s[j]==s[i])

                        curLen = i-j;break;

                    else

                        myHash.erase(s[j]);

            else

                curLen++;

                if(LongestLen<curLen)LongestLen=curLen;

                myHash.insert(s[i]);

        return LongestLen;

};

代碼一次AC,很爽！

LEETCODE、我的算法在最壞情況下的時間復雜度是不好描述，肯定是大于O(N)的，但是我覺得肯定是小于O(NlgN)的，回搜的代價不會太大，但是我總是在想是不是有其他的精妙的解法呢，結果在網上還真找了個，在discuss里面有個算法，乍一看沒看懂：
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> pos(256, -1);
        int begin = 0, ret = 0;
        for (int i = 0; i < s.size(); ++i) {
            begin = max(begin, pos[s[i]] + 1);
            pos[s[i]] = i;
            ret = max(ret, i - begin + 1);
        }
        return ret;
    }
};

看了幾分鐘之后拍案叫絕，這個實際上也是一個hash表（即pos），它hash的高明之處是不用回搜，之所以不用回搜，是因為他用pos存放了每個字符最近一次出現時候的位置。

可以看出，大數據集的速度提高了一倍，這也可以看出我的算法回搜的平均長度其實不是很大，當然也是因為我用一個變量記錄了可能的回搜范圍，不過依然沒有這個精妙。