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

题意

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路

• 滑动窗口[left,j)
• set是用来保存string的[left,j)中的不重复的元素
• 若string[j]已存在于set中，需要删除该重复元素，及它之前的所有元素
• 若string[j]未存在于set中，把string[j]插入set中，并更新ans=max(ans, j-left+1);

代码

int lengthOfLongestSubstring(string s) {
        int left = 0;
        int ans = 0;
        set<char> tmp_s;
        for(int j = 0; j<s.size(); j++){
             // 一旦s[j]为重复元素，且记[i,j)范围内另一个元素下标为x,则删除[i,x]范围内的所有元素
            while(tmp_s.count(s[j])){
                tmp_s.erase(s[left]);
                left++;
            }

            tmp_s.insert(s[j]);
            ans = max(ans, j-left+1);
        }
        return ans;
    }