3. 无重复字符的最长子串

解法1:滑动窗口+保存索引

class Solution {
public:
    // 
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        int left = -1, right = 0;
        int ret = 0;
        unordered_map<char, int> mp;
        while (right < len) {
            auto pos = mp.find(s[right]);
            if (pos == mp.end() || (pos->second <= left)) {
                ret = max(ret, right - left);
            } else {
                left = mp[s[right]];
            }
            mp[s[right]] = right;    
            ++ right;
        }
        return ret;
    }
};

解法2:滑动窗口+保存次数

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int left = 0, right = 0;
        int len = s.size();
        int ret = 0;
        while (left < len && right < len) {
            if (mp.find(s[right]) == mp.end() || mp[s[right]] == 0) {
                ++ mp[s[right]];
                ++ right;
                ret = max(ret, right - left);
            } else {
                -- mp[s[left]];
                ++ left;
            }
        }
        return ret;
    }
};

解法3:滑动窗口+保存次数

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int ret = 0;
        while (right < s.size()) {
            char cur = s[right];
            ++ right;
            window[cur] ++;
            while (window[cur] > 1) {
                char temp = s[left];
                window[temp] --;
                ++ left;
            }
            ret = max(ret, right - left);
        }
        return ret;
    }
};