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）