无重复字符的最长子串的长度

参考https://baijiahao.baidu.com/s?id=1596959005481205984&wfr=spider&for=pc
给定一个字符串，请找出其中无重复字符的最长子字符串。

样例

例如，在”abcabcbb”中，其无重复字符的最长子字符串是”abc”，其长度为 3。

对于，”bbbbb”，其无重复字符的最长子字符串为”b”，长度为1。

1、暴力法

#include<iostream>
#include<string>
#include<set>
using namespace std;

class Solution {
public:

    bool isUnique(const string &s, int start, int end){
        set<char> charSet;
        for (int i = start; i < end; i++) {
            if (charSet.find(s[i]) != charSet.end()) {
                return false;
            }
            charSet.insert(s[i]);
        }
        return true;

    }

    int lengthOfLongestSubString(string s) {
        int nLen = 0;
        int maxLen = 0;
        nLen = s.size();

        for (int i = 0; i < nLen; i++) {
            for (int j = 0; j <= nLen; j++) {
                if (isUnique(s, i, j)) {
                    maxLen = maxLen < (j - i) ? (j - i) : maxLen;
                }
                else {  //继续以下一个字符作为首字符
                    break;
                }
            }
        }

        return maxLen;

    }
};


int main()
{

    string str;
    getline(cin, str);

    Solution so;
    int maxLen = so.lengthOfLongestSubString(str);
    cout<< maxLen << endl;

    return 0;

}

2、优化

1、当前搜索字符到字符串结尾长度小于等于当前以获取最大长度maxLen时，这时候maxLen即为算法的结果，可以直接返回结果，如上面第四轮后面长度为3当内层循环已经检索到字符串尾部时，证明最长无重复子串已经获取，可以直接返回结果。
2、解决思路二上面的算法每一轮只移动一个字符，是不是要挨个字符作为子串首字符一一判断呢？我们看下面情况，当在位置5出现重复字符x时，我们在重复字符x（位置2）之前搜索仍然会在位置5处重复，因此我们可以把上一个重复字母的index+1(即图中的3)作为新的搜索位置，这样我们每次只需改变新的开始索引位置（即图中橘黄色箭头），而当前搜索位置（即图中绿色箭头）不用变，继续往下搜索，因此效率大大提升。

#include<iostream>
#include<string>
#include<map>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubString(string s) {
        map<char,int> chmap;    //记录字符上一次出现的位置

        int start = 0; //记录当前子串的开始位置


        int maxLen = 0; 

        for (int i = 0; i < s.size(); i++) {

            if (chmap.find(s[i]) != chmap.end()) {  //当前元素重复
                maxLen = maxLen > (i - start) ? maxLen : (i - start);
                start = chmap[s[i]] + 1;    //移动当前位置到上一个重复元素的下一位
            }

            chmap[s[i]] = i;    //记录当前字符的位置

        }

        //最后一次别忘了
        return maxLen > (s.size() - start) ? maxLen : (s.size() - start);

    }


};


int main()
{

    string str;
    getline(cin, str);

    Solution so;
    int maxLen = so.lengthOfLongestSubString(str);
    cout<< maxLen << endl;

    return 0;

}