题目描述

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

样例

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

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

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

算法1

哈希表＋双指针

时间复杂度

O(n)

C++ 代码

class Solution {
public:
/*
根据题意可知，字符串存在空和只有一个字符的情况，则需要特判

a   b   c   b   a   d
1
2   2   2   2' 
2   2*  2   2'  
        1   
            2   2   2
下标    2   3   4   5
ans：4  ->  c b a d

指针2走到2'时，该元素在哈希表中出现过，即是一个重复字符
则前面的abc是一个非重复子串，更新答案
找出哈希表中与2'重复的字符的下标，即2*，此时2*的b及它前面的元素不再具有成为下一个非重复子串的可能
更新下一个非重复子串的起始位置，即 更新指针1为2*+1，即重复下标+1
我们的更新答案写在if判断中，它只有遇到重复字符才会更新答案，如果之后遇不到重复字符呢，如果一开始就没有重复字符呢？
因此在else中我们需要考虑当前不重复子串的长度是否可以成为新的ans


1、设置两个指针，指针1、指针2分别表示一段非重复子串的起始位置和末尾位置的下一个
    指针1和指针2一开始都指向第一个元素，指针2开始遍历
2、如果当前遍历到的元素在哈希表中没有出现过，则将其放入哈希表中
    **还需要考虑 遍历时一直不出现重复的字符如何更新答案：记录不重复子串的长度
3、如果当前遍历到的元素在哈希表中出现过
        ① 用指针2-指针1得到这一段不重复的子串长度，更新ans
        ② 在哈希表中找出与当前元素重复的字符的下标，将哈希表中该下标及之前的元素都删掉(即把旧重复字符及其之前的字符全部在哈希表中删除)
            【出现了重复元素，则旧重复元素成为已经处理过的答案，因此旧元素及之前的元素都需要被删掉】
        ③ 指针1变为重复下标的下一个
        ④ 更新不重复子串的长度，防止之后遍历遇不到重复元素而忘记更新答案
        ⑤ 将当前元素放入哈希中(考虑到此步骤和上述2的行为相同，则合并在判断后写)
*/


    int lengthOfLongestSubstring(string s) {
        int nIndex1=0,nIndex2=0,nIndex=0;
        unordered_map<char,int> hash;
        int nAns=0,nRes=0;
        while(nIndex2<s.size())
        {
            if(hash.find(s[nIndex2])!=hash.end()) // 如果哈希表中存在当前元素
            {
                // 更新答案
                nAns=max(nAns,nIndex2-nIndex1);
                nIndex=hash[s[nIndex2]];
                for(int i=nIndex1;i<=nIndex;i++) // 根据旧元素的下标及序列开始下标删除已考虑过的答案
                {
                    hash.erase(hash.find(s[i]));
                }
                nIndex1=nIndex+1; // 更新下一个非重复子串的起始下标
            }
            else // 哈希表中不存在该字符，也需要更新非重复字串的长度
            {
                nAns=max(nAns,nIndex2-nIndex1+1);
            }
            hash[s[nIndex2]]=nIndex2; // 将当前元素放入哈希表
            ++nIndex2;
        }
        return nAns;
    }
};

算法2

哈希表＋双指针

1、如果i’所对应的j’在j的左边，即i’到j’之间不包含任意一个重复字符，这样会有矛盾，会得出从i到j’之间也不会有重复字符，和我们假设的i到j是最长无重复字符的子串不符。

2、因此i’所对应的无重复子串的左端点要么在j位置，要么在j的右边。

3、每次枚举完i之后，再枚举新的i’时，可以直接从上一个j的位置直接往后枚举，这样指针j不会走回头路，同时也保证两个指针都只会走n次，即O(n)

用一个哈希表维护j到i中每个字符出现的次数，每次i向后移动一格时，将i+1对应的字母加到哈希表中，然后判断哈希表中是否有与S[i+1]重复的元素，有的话，则把j往后移动，直到移动到某个和S[i+1]重复的元素为止，然后把这些元素踢出哈希表

该方法和方法1的不同在于，方法1的哈希表中value记录字符出现的下标位置，方法2记录的是value出现的次数，删除时，删除的元素都是相同的，只是删除的判断和代码不同，但方法2更简洁，且很通用

时间复杂度

时间复杂度：O(n)
空间复杂度：O(n)

C++ 代码

class Solution {
public:

    int lengthOfLongestSubstring(string s) {

        unordered_map<char,int> heap;
        int nRes=0;
        for(int i=0,j=0;j<s.size();j++)
        {
            // 如果出现了重复字符，将重复及之前的都从哈希表中删掉
            if(heap[s[j]])
            {
                while(heap[s[j]]) heap[s[i++]]--;
            }
            // 没有出现过，则放入哈希表，并更新答案
            ++heap[s[j]];
            nRes=max(nRes,j-i+1);
        }
    return nRes;
    }
};