Ex48 最长不含重复字符的子字符串

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

解题思路

建立一个map，不过是用长度为256的vector表示的，vector的每个index是char的数字表示，内容是其出现的位置。初始化为-1，代表此字符未出现。因此，我们遍历string的每一个位（即char），有以下三种情况：

• 相应的hash_table中的位置<0（-1），length加一；
• 相应的hash_table中的位置不为-1，但之前的位置不在本次的范围之中（index - prev_index > length），length加一；
• 相应的hash_table的位置不为-1，之前的位置在本次的范围之中，length更新为index - prev_index。

代码

class Solution {
 public:
  int lengthOfLongestSubstring(std::string s) {
    if (s.size() <= 0) return 0;
    int max = 0, length = 0;
    int ssize = s.size();
    std::vector<int> hash_table(256, -1);
    int index = 0;
    while (index < ssize) {
      int prev_index = hash_table[s[index]];
      if (prev_index < 0 || index - prev_index > length) {
        ++length;
      } else {
        max = max > length ? max : length;
        length = index - prev_index;
      }
      hash_table[s[index]] = index;
      ++index;
    }
    return max > length ? max : length;
  }
};

结果

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了93.42%的用户

内存消耗：8.5 MB, 在所有 C++ 提交中击败了49.33%的用户

备注

和《剑指Offer》上不同的一点是，这里的题目扩展到所有的字符，不只限于’a’~’z’。