阴沟翻船题——Longest Substring Without Repeating Characters-二、题解思路

2.1 题目大意

给一个字符串，找到一个最长的自串，使这个子串没有重复的字符。

2.2 方案1——2重循环求解

由于assic码字符范围只有0~255，那么我们可以用一个bool[] 数组，记录特定字符是否已经使用过。
每重循环，查找以i开头的字符串，最长走到哪里没有重复字符。

int Solution3::lengthOfLongestSubstring(std::string s)
{
    int maxLen = 0;
    for (int i = 0; i < s.size(); i++) {
        bool arr[256];
        memset(arr, 0, sizeof(bool) * 256);
        int curLen = 0;
        for (int j = i; j < s.size(); j++) {
            char c = s[j];
            if (!arr[c]) {
                arr[c] = true;
                curLen++;
            }
            else {
                break;
            }
        }
        maxLen = max(maxLen, curLen);
    }
    return maxLen;
}

2.3 方案2——一次循环模拟

2.2是个O(n^2)的算法，我们能否优化以下么？
以abcabcabdd为例子，我们只看i=0时的循环，当i=3时，当前字符为a，在之前出现过了。
我们是否可以再定义一个起始指针beg，当出现重复的字符时，我们把beg指针后移，并且置空beg位置字符的标志位，直到beg处的字符和i处的字符相同。
基于这个想法，就有了这段代码：

int Solution3::lengthOfLongestSubstring_effective(std::string s)
{
    bool arr[256];
    memset(arr, 0, sizeof(bool) * 256);
    int beg = 0, idx = 0;
    int sizeN = s.size();

    int maxRes = 0;
    int curRes = 0;

    while (idx < sizeN) {
        char c = s[idx];
        if (arr[c]){
            maxRes = max(maxRes, curRes);
            char bc;
            do{
                bc = s[beg];
                arr[bc] = false;
                curRes--;
                beg++;
            }while (beg < idx && bc != c);
        }
        curRes++;
        arr[c] = true;
        idx++;
    }
    maxRes = max(maxRes,curRes);
    return maxRes;
}