题目分析

题目链接：

这道题目主要难点在于这样一个问题：

a, b, c, d, e, f, c, g, h, ...我从第一个字符开始检查，已经检查到f了，目前为止还没有出现重复字符：[a, b, c, d, e, f,] c, g, h, ...检查到下一个c时，发现它在前面已经出现过了（至于如何判断新字符是否已经出现过，我们在下面讨论）：[a, b, c, d, e, f, c,] g, h, ...这时应该怎么办？下一次检查哪个子串？这时将子串的右端点右移是错误的，因为这样子串中依然包括两个c：[a, b, c, d, e, f, c, g,] h, ...正确的方式是将子串左端点右移，使它不包含两个成重复的字符：a, b, c, [d, e, f, c,] g, h, ...然后再将右端点右移，继续检查：a, b, c, [d, e, f, c, g,] h, ...

那么如何判断新字符是否已经在子串中出现过呢？

我们可以使用Map<char, bool>，它的原理是：将每个字符作为一个节点存在一颗二叉树中，尝试插入新字符的节点，如果出现冲突（树中已经有相同字符的节点），则表明新字符已经出现过。每次判断的复杂度为log(m)，m为子串的最大长度。在进行子串左端点右移的时候，要记得将被移出的字符从map种删掉。还有一种更高效的查找方法：哈希表。在这道题使用哈希表有天然的优势：char的范围是已知的、较小的——[0, 255]（unsigned char）。那么就可以直接用一个bool[256]数组来存储每一种字符是否已出现。在进行子串左端点右移的时候，要记得将被移出的字符重新标记为未访问。

以上两种方法在进行子串左端点右移的时候都要进行重置操作，为了避免它，我们不存储bool(是否出现过)，而是存储int(上次出现的下标)。详见下面的代码部分。

代码

class Solution {public:    int lengthOfLongestSubstring(string s) {        map
    
      last_appear_index;        int sub_string_start = 0, max_length = 0;        map
     
      ::iterator it;        for (int i = 0; i < s.length(); i++) {            it = last_appear_index.find(s[i]);            if (it != last_appear_index.end() && it->second >= sub_string_start) {                sub_string_start = it->second+1;            }            last_appear_index[s[i]] = i;            max_length = max(max_length, i-sub_string_start+1);        }        return max_length;    }};
     
    

虽然使用bool[256]更加高效，但是作为算法题，不应该对用户可能输入的字符做任何猜测（在其他语言中，字符可能不用整数表示），使用map<char, int>是更通用的方法。