题目描述
给定一个字符串，请找出最长的不包含重复字符的子串。
请注意子串和子序列的区别：
- 子串一定是连续的一段
- 子序列不一定是连续的一段，但下标要求是递增的
样例
给定 "abcabcbb"，答案是"abc"，长度是3.
给定 "bbbbb"，答案是"b"，长度是1.
给定 "pwwkew"，答案是"wke"，长度是3.
算法
(双指针扫描) $O(n)$
定义两个指针 $i, j (i <= j)$，表示当前扫描到的子串是 $[i, j]$ (闭区间)。扫描过程中维护一个哈希表unordered_map<char,int> hash，表示 $[i, j]$中每个字符出现的次数。
线性扫描时，每次循环的流程如下：
- 指针 $j$ 向后移一位, 同时将哈希表中 $s[j]$ 的计数加一:
hash[s[j]]++; - 假设 $j$ 移动前的区间 $[i, j]$ 中没有重复字符，则 $j$ 移动后，只有 $s[j]$ 可能出现2次。因此我们不断向后移动 $i$，直至区间 $[i, j]$中 $s[j]$ 的个数等于1为止；
复杂度分析：由于 $i, j$ 均最多增加n次，且哈希表的插入和更新操作的复杂度都是 $O(1)$，因此，总时间复杂度 $O(n)$.
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
int res = 0;
for (int i = 0, j = 0; j < s.size(); j ++ )
{
hash[s[j]] ++ ;
while (hash[s[j]] > 1) hash[s[i ++ ]] -- ;
res = max(res, j - i + 1);
}
return res;
}
};
二刷，看了Y总的题解，真是简洁明了~
谢谢hh
阎总，还是建议以后可以对比较难理解的代码重点解释一下，比如这一题的hash[s[i ++ ]] –这一句就不太好理解，看了好一会儿才明白是为什么。
好滴，加油hh 很多代码都有有固定模式的，第一次见都会比较陌生，多见几次就熟悉了hh
基础太不好，看了好一会儿才看到妙处，最精彩的是 hash[s[i++]]— 这一句，比如“abcacbb”测试用例，运行至“ac”这一字段时，除了s[‘a’] 和s[‘c’]，s[‘b’]已经置零了，这为后续的‘b’做了铺垫，也满足了s[子段字符]=1, s[其余字符]=0的根本要求。
理解得不错，加油！孰能生巧。
hash[s[j]] > 1， 为什么这一步，用hash.count(s[j]) > 1就会错呢
count返回值为bool类型只会是0或者1
感谢回复
Y总，太棒啦！
y总，这里为什么开一个int数组去记录字符出现的次数会报错呀
因为这里的字符不止是小写字母，你没处理好哈希吧
三刷的进来了,论哈希表和双指针的综合运用
厉害啊
res = max(res, j - i + 1); 这个好像每次都要执行哈, 感觉可以改造哈: [i,j]没有重复元素, [i,j+1]存在重复元素时, 计算max就可以了哈
这句话里只有常数次计算，所以每次都计算也是没关系的，不影响时间复杂度。
赞
谢谢hh
66666666666
acwing给的答案就是很精简，巧妙
哈哈谢谢！
膜拜闫神，就喜欢这样清晰脱俗的代码风格。
哈哈感谢！
太巧妙
这是一个通用的“滑动窗口 + 哈希表”的套路~
评论测试demo1
评论正常吧hh
评论还有闪动效果?在评论测试一下
哈哈，为了醒目一点
真巧妙,nb
这个解法很简洁， 棒！
谢谢！
Wow! I really can’t believe that you can solve this problem in such a clever way！
如此简洁。。。我估计面试官一遍都看不大明白
面试官说，解释一下吧~~
哈哈哈，要坚信自己遇到的面试官都很nice
哈哈，我得好好打磨自己，对得起善良的面试官