无重复字符的最长子串

Category	Difficulty	Likes
algorithms	Medium (38.85%)	7781

Companies

adobe | amazon | bloomberg | yelp

Required

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

Cases

示例 1:

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

示例 2:

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

示例 3:

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

Tips

$0<=s . length <=5 * 10^{4}$
$s$ 由英文字母、数字、符号和空格组成

AC 双指针

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int res = 0;
        unordered_map<char, int> hash;
        for (int i = 0, j = 0; j < s.length(); j++)
        {
            hash[s[j]]++;
            while (hash[s[j]] > 1)
                hash[s[i++]]--;
            res = max(res, j - i + 1);
        }
        return res;
    }
};

使用无序的map映射建立哈希表

i，j两个指针，当 j 指针大于1以后， i++ ，直到 j 指针所在的字符等于1。

AC 滑动窗口

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        if (s.length() <= 1)
            return s.length();
        unordered_set<char> set;
        int result = 0;
        int i = 0, j = 0;
        for (i = 0; i < s.length(); i++)
        {
            while (set.find(s[i]) != set.end())
            {
                set.erase(s[j]);
                j++;
            }
            set.insert(s[i]);
            result = max(result, int(set.size()));
        }
        return result;
    }
};

使用无序set建立集合，
当set集合包含重复字符时，收缩窗口。

滑动窗口和双指针的区别

滑动窗口可能也需要两个指针，但是他并不是双指针问题，类似的有“分治问题”，我们也常常使用两个指针，如快速排序。
双指针的处理呢，是与端点有关，而滑动窗口是区间，因而滑动窗口解决的是问题本身。

滑动窗口并不是双指针的子集，二者没有任何关系。