【剑指 offer】最长不含重复字符的子字符串（双指针）

1、题目描述

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

假设字符串中只包含从’a’到’z’的字符。

样例:

输入："abcabc"
输出：3

2、问题描述：

3、问题关键：

• 双指针做法， 一个前j，一个后i， 求最长的区间（ j - i + 1 ）。
• 便于查找，可以用一个hash表，如果遇到重复的，移动i直到，不再出现重复的。

4、C++代码：

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char, int> m;//hash表便于查找。
        int res;
        for (int i = 0, j = 0; j < s.size(); j ++) {
            while(m[s[j]]) m[s[i ++]] --;//如果出现重复的，那么移动i直到不再出现重复的为止。
            m[s[j]] = 1;//否则，记录到hash表中，
            res = max(res, j - i + 1);//记录最长的区间。
        }
        return res;
    }
};