剑指offer 49. 最长不含重复字符的子字符串

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

假设字符串中只包含从 a 到 z 的字符。

数据范围

输入字符串长度 [0,1000]。

样例

输入："abcabc"

输出：3

方法一：双指针+哈希表 O(n)

思路如下：

1. 设置两个指针，i 为右端点，j 为左端点，从前往后遍历每一个字母。
2. 每次遍历都先看看当前的字母是否在 j ~ i-1 区间中出现过，这里用哈希表来判断。如果出现过，就将左端点 j 往后移，并将 j 所在的字母在哈希表中删除，直到删除了 i 所在的字母为止。
3. 将 i 所在的字母加入哈希表中。
4. 计算当前最长字符串，更新最大值。

我们举一个例子，假设给定一个字符串 a b c a e ，具体步骤如下：

第一步： 由于哈希表为空，将 a 加入哈希表中，且 ans = 1 。

第二步： 通过查找哈希表发现 b 之前没有出现，故将 b 加入哈希表中，且 ans = 2 。

第三步： 通过查找哈希表发现 c 之前没有出现，故将 c 加入哈希表中，且 ans = 3 。

第四步： 通过查找哈希表发现 a 之前已经出现在哈希表中，将指针 j 后移一位并将对应位置的字母在哈希表中的值置 0 。结果发现置 0 的字母就是 a ，所以退出 while 循环。

再将 a 加入哈希表中，此时 ans 仍然为 3 。

第五步： 通过查找哈希表发现 e 之前没有出现，故将 e 加入哈希表中，且 ans = 4 。此时已经遍历到最后，所以最长不含重复字符的长度为 4 。

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        int n = s.size(), ans = 0;
        unordered_map<char, int> st;
        for (int i = 0, j = 0; i < n; i++)
        {
            while (st[s[i]])  st[s[j++]] = 0;
            st[s[i]] = 1;
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

欢迎大家在评论区交流~