3---无重复字符的最长字串

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 0 < = s . l e n g t h < = 5 ∗ 1 0 4 0 <= s.length <= 5 * 10^{4} 0<=s.length<=5∗104
• $s$ 由英文字母、数字、符号和空格组成

本题使用双指针算法和哈希表

class Solution {
public:int lengthOfLongestSubstring(string s) {// 以子串的最后一个字母来分类, 一共可以分成n类, 一次处理一类即可// 对于每一个结尾i, 都需要往前找到一个最小的j, 使得 j ~ i之间没有重复的字母(n^2)// 所有双指针算法的优化思路都是一样的, 就是考虑是否有单调性unordered_map<char,int> heap; //使用哈希表维护 j ~ i之间的元素是否有重复int res = 0;for(int i = 0,j = 0;i < s.size();i++){heap[s[i]] ++;while(heap[s[i]] > 1) {heap[s[j++]] -- ;// 新的以i为结尾的子串的j, 必然不可能往回走}res = max(res,i - j + 1);}return res;}
};