题目描述

blablabla

样例

blablabla

算法1

(双指针算法) $O(n)$

这题目一开始看了好几遍视频都没懂，关键在于加粗的部分

双指针算法：

思路是 维护一个 i ~ j 的区间，使用hash_map 来确保 i~j之间的数都是不重复的。

每当j往后移动一个位置后。检查有没有重复的，如果没有重复更新j-i+1 为最大答案。如果有重复，从i开始一路删 删到 和j一样值（count>1）的位置。那么再删除当前(因为s[j]和这个一样)，移动到下一个位置重新开始移动J

C++ 代码

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char,int> count;
        int res =0;
        for(int i = 0, j = 0; j < s.size(); j++){
            if( ++count[s[j]] > 1){
                while(count[s[i]] == 1) count[s[i++]]--; //一路删到 ！=1

                count[s[i++]] --;// 把当前的点删掉然后从下一个位置继续
            }
            res = max(res,j - i + 1);
        }
        return res;
    }