set&&劍指 Offer 48. 最長不含重複字元的子字元串

做過類似題目。

1.set

過了，但是備援操作占用比較大的時間複雜度。發現set的size()方法傳回值不是(signed) (int)類型，而是unsigned long (int)類型。參考：C++ 檢視變量資料類型之 typeid().name()

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //做過類似題目，用set試試
        set<char> str;
        int i=0,j=0,ans=0;
        while(i<s.length()&&j<s.length()){
            if(str.insert(s[j]).second==false){
                i++;
                j=i;
                str.clear();
            }
            str.insert(s[j]);
            ans=max(ans,(int)str.size());
            j++;
        }
        return ans;
    }
};
           

2.哈希表及其他解法，參考：面試題48. 最長不含重複字元的子字元串（動态規劃 / 雙指針 + 哈希表，清晰圖解）

原來隻需要固定右坐标，dp[i]表示以s[i]結尾的最長無重複字元子串長度。

（2/8）