【LeetCode】3. 無重複字元的最長子串

文章目錄

• 題目連結
• 注意點
• 解法
• 遇到問題
• 小結

題目連結

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

注意點

解法

解法1：散列法

利用256的數組存儲字元串中每個字元的出現位置，初始值未-1，表示沒有出現過。

若是目前周遊字元沒有出現過，則将出現位置更新；

若是目前周遊字元出現過，則說明出現了重複字元，，計算無重複字元串的長度，并更新無重複字元串的起點，最後将該字元出現位置更新。

這裡注意，更新起點後，在舊起點和新起點之間的字元的出現位置要置為-1。

執行用時 :

12 ms

, 在所有 C++ 送出中擊敗了

81.27%

的使用者

記憶體消耗 :

8.5 MB

, 在所有 C++ 送出中擊敗了

100.00%

的使用者

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> hash(256,-1);
        int start=0,res=0;
        if(s.size()==0) return 0;
        for(int i=0;i<s.size();i++){
            if(hash[s[i]]!=-1){
                res=max(i-start,res);
                while(start<hash[s[i]]+1){
                    hash[s[start++]]=-1;
                }
            }
            hash[s[i]]=i;
        }
        res=max((int)s.size()-start,res);//因為寫代碼時是遇到重複的才計算res,是以可能出現整個字元串都沒有重複字元的情況，故最後循環結束要再計算一次res
        return res;
    }
};
           

遇到問題

因為寫代碼時是遇到重複的才計算res,是以可能出現整個字元串都沒有重複字元的情況，故最後循環結束要再計算一次res。

小結

利用hash數組存儲字元出現的位置

動态維護無重複字元串的起點