原题描述

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3.

O(N)算法

拿到这个题之后可以分析一下最长不重复字串的特性：任何一个不重复字串一定是在两个重复字符之间（PS:大家会说如果整个字符都不重复的情况呢？这点在后面具体算法中会解决）。可以想象在整个搜索的过程是需要判断字符有没有出现过，这个很容易想到用Hash表来作为O(1)的查找，但是当我们仔细分析之后发现，字符的ASCII码只有256个值，所以就可以使用一个256长度的last数组来直接代替Hash表。
$s$为字符串数组，$ans$作为最大无重复字符串长度，即合法字符串长度
具体的算法如下：
1. 初始化$last$数组用来存储上次出现该字符的$index$，初始化一个$left = 0$作为当前合法字符串的最远左边界
2. 遍历整个数组，遍历$index$为$i$
3. 如果$last[s[i]] >= left$，则证明在当前扫描的字符串中存在重复字符，那么将合法字符串的最优左边界重新赋值$left = last[s[i]] + 1$ 继续步骤4
4. 对last数组赋值$last[s[i]] = i$
5. 最大合法长度$ans$是上次的最大合法长度和当前扫描的合法字符串长度$i - left + 1$之间的较大值，继续遍历步骤2
6. 遍历退出，返回ans
(PS:可以发现如果整个字符串都是合法的，该算法仍然是work的）

C++代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 题意为求不包含重复字符的最长子串
        // left用以记录合法的最远左边界位置，last记录字符上一次出现的位置
        int ans = 0, left = 0, len = s.length();
        int last[255];
        memset(last, -1, sizeof last);
        
        for (int i = 0; i < len; i++) {
            // 上次出现位置在当前记录边界之后，即该子串中出现了重复字符，需调整left使得子串合法
            if (last[s[i]] >= left) left = last[s[i]] + 1;
            last[s[i]] = i;
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};

Bug Free Procedure 从记事本直接写代码

2016.11.30 Bingo!!!一次性AC

2016.12.01 语句混乱+一次性AC
1. 记住相应的返回值$ans$要事先定义

2016.12.04 逻辑错误
1. $last$数组一定要记得及时更新

2016.12.14 Bingo！！！一次性AC