3. Longest Substring Without Repeating Characters【medium】

解题思路：

暴力解法 O(N^3)：

从每个点遍历、依次遍历这个点后的每一个点、通过遍历该点之前的点判断该点是否出现过。听上去有点拗口，代码在下方，这个暴力方法Leetcode也可以AC，但是不推荐使用。

**头尾标记法 O(N*logN)：**

头标记指向当前最长无重复字符串的头部，尾标记指向其尾部。通过一个 map 来记录出现过的字符最后出现的位置。

依次遍历数组，如果当前字符已出现过，则让头标记指向其最后出现过的位置的后一个位置。然后每次通过头、尾标记计算当前无重复字符串的长度，并与已知最大值作比较。这里查询map的复杂度为 O(logN)，遍历的复杂度为 O(N)，因此整体复杂度为 O(N*logN)。如果这里使用hash_map可以将查询复杂度降低到O(1)，从而使得整体复杂度为O(N)，但是hash_map不是标准的C++库，所以这里没有使用。

实现代码：

// 3. Longest Substring Without Repeating Characters
// 暴力解法
int lengthOfLongestSubstring_bruteForce(string s) {
  int res = 0, sum;
  for (int i = s.size() - 1; i >= 0; i--) {
    sum = 1;
    for (int j = i - 1; j >= 0; j--) {
      bool flag = true;
      for (int k = i; k > j; k--) {
        if (s[j] == s[k]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        sum++;
      } else {
        break;
      }
    }
    res = max(res, sum);
  }
  return res;      
}
// 头尾标记法
int lengthOfLongestSubstring(string s) {
  map<char, int> myMap;
  int res = 0;
  for (int i = 0, j = 0; j < s.size(); j++){
    if (myMap.find(s[j]) != myMap.end()) {
      i = max(i, myMap[s[j]] + 1);
    }
    myMap[s[j]] = j;
    res = max(res, j - i + 1);
  }
  return res;
}

问题描述：

Given a string, find the length of thelongest substringwithout 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. Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.

3 Longest Substring Without Repeating Characters