题目内容

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

示例

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

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

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

示例 4:
输入: s = “”
输出: 0

提示

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

题解

采用双指针问题进行求解。
在双指针或者滑动窗口算法中，需要思考的就是如何能够枚举子串不重不漏，最后找到题目的答案。在本题中，可以通过以子串的尾结点为分类标准，比如尾结点的下标为0，为1，为2，…，直到枚举完毕，然后每次处理1类的问题，最后求全局最优解即可。在本题具体问题中，当枚举以i为尾结点的所有子串的时候，有这个结论，即当i往后移动后，对应的不重复子串要么不动，要么往后移动。因此，我们就可以通过这个属性将每个字串的最大不重复子串的长度找出来，然后求全局最大值即可。

证明：当i和j指针包含的子串达到最大不重复子串要求时，i指针往后移动后，j指针一定要么不动要么往后移动。
因为当i往后移动后，只有两种情况：
1、i往后走的下一个字符在子串中没有出现，那么j就不移动，仍然符合最大不重复子串的要求
2、i往后走的下一个字符在子串中出现，那么j往左移动就一定不是题目要求，因为子串中一定包含重复元素，因此，j只能往后移动，直到其内部子串达到不重复为止。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> heap;//用hash表统计一下每个字符出现的次数
        int res = 0;
        for(int i = 0, j = 0; i < s.size(); i++){
            heap[s[i]]++;
            while(heap[s[i]] > 1){
                heap[s[j++]]--;
            }
            res = max(res,i-j+1);
        }
        return res;
    }
};