Leetcode 剑指 Offer 48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：

s.length <= 40000

方法一：利用 hashset 来检查重复元素。

1. 我们定义 left 和 right 两个指针表示一个特定的子字符串的首和尾。初始它们都在索引 0 处。
2. 移动 right，并同时向 hashset 中添加 right 所指的元素值，当 right 指到重复的元素时，right - left 的值就是一个不含重复字符的子字符串的长度。
3. erase 掉 haseset 中的 left 所指元素的值，然后让 left++（for 循环的作用）。之后继续移动 right 来找到下一个不含重复字符的子字符串的长度。

先放C++代码，思路清晰明了。

#include<iostream>
#include<unordered_set>
#include<string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() <= 1) {return s.length();}

        int res = -1, right = 0;
        unordered_set<char> store;//store.count(),store.insert(),store.erase()的用法

        for(int left = 0; left < s.length(); ++left) {
            while(right < s.length() && !store.count(s[right])) {
                store.insert(s[right]);
                ++ right;
            }

            res = max(res, right - left);
            store.erase(s[left]);

            if(right >= s.length()) {break;}
        }

        return res;
    }
};


int main()
{
    string mystring="abcabcbb";
    Solution S;
    cout<<S.lengthOfLongestSubstring(mystring)<<endl;
    system("pause");
    return 0;
}