3 无重复字符的最长子串

文|Seraph

01 | 问题

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

示例 1:

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

示例 2:

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

示例 3:

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

02 |解题

初解：

一开始的思路是利用一个map保持子串，里面存着计数从前往后遍历字符串时，保存着最新的无重复最长子串信息。当遇到相同的字符，需要删除与当前字符相同字符之前的所有子串（包含该相同字符）。并从该字符后一个字符开始从新计算。
检索完所有的字符，即能得到无重复最长子串结果。map的尺寸最大时，即为最长子串。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> mapSub;
        int i=0, j=0, max=0;
        while(i<s.size())
        {
            if(mapSub.find(s[i]) == mapSub.end())
            {
                mapSub[s[i]]=i;
            }
            else
            {
                if(mapSub.size()>max)
                {
                    max=mapSub.size();
                }
                int index;
                for(index=j; index<=mapSub[s[i]]; index++)
                {
                    mapSub.erase(s[index]);
                }
                j=index;
                mapSub[s[i]]=i;  
            }
            i++;
        }
        if(mapSub.size()>max)//最长的子串包含最后一个数时，while会提前跳出，不会计算，故在此计算一遍
            max=mapSub.size();
        return max;
    }
};

做的过程中，未考虑当最长的子串包含最后一个数时，while会提前跳出。
同时，经常做题的时候，总是考虑不全面，老是以自以为的特例来写代码过程，导致需要提交很多次，才能从错误用例中，一个一个改正确才通过。

再解：

上述解法没有任何问题，但是条件判断不恰当，导致代码条数过多，同时利用好正确的判断依据，其实是可以使用set容器的，只要我们能每次遇到相同的字符时，删除set容器中的变量直到将前一个相同字符删除即可，如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int n = s.size();
        unordered_set<char> setChar;
        int i=0,j=0,max=0;
        while(i<n&&j<n)
        {
            if(setChar.find(s[i]) == setChar.end())//未发现该字符
            {
                setChar.insert(s[i++]);
                if(i-j > max)
                    max = i-j;
            }
            else//发现相同的字符，直到删除前一个保存的相同值
            {
                setChar.erase(s[j++]);
            }
        }
        return max;
    }             
};

以上两种方法整体来说，就是一种常用到的滑动窗口的方法。

终解：

其实初级利用到了一点就是map能存下标的方法，当我们遇到相同的字符时，能立即知道前一个相同字符的下标，但是处理的时候依然要逐个删除map中的值，所以效率相对于而没有提升。
但是我们可以利用字符的有限性（0~127），定义字符到索引的映射。每次遇到相同的字符时，不需要删除字符，只需要更新当前字符坐标就行。

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        vector<int> v(128,0);
        int j=0, int iMax=0;
        for(int i=0;i<s.length();i++)
        {
            j=max(j, v[s[i]]);
            iMax=max(iMax, i-j+1);
            v[s[i]]=i+1;
        }
        return iMax;
    }             
};

03 | 积累知识点

1 不仅要考虑边界用例，也要考虑程序中循环的终止条件可能对边界用例的影响。
2 多举自己实例，从而让自己了解可能未识别到的用例范围。