3.2 无重复字符的最长子串

问题

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入:

s = "abcabcbb"

输出:

3 

解释:

因为无重复字符的最长子串是 `"abc"`，所以其长度为 3。

示例 2:

输入:

s = "bbbbb"

输出:

1

解释:

因为无重复字符的最长子串是 `"b"`，所以其长度为 1。

示例 3:

输入:

s = "pwwkew"

输出:

3

解释:

因为无重复字符的最长子串是 `"wke"`，所以其长度为 3。
请注意，你的答案必须是 **子串** 的长度，`"pwke"` 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

分析

使用“滑动”指针（滑动窗口）的方法就能进行处理。
问题只要求输出长度，即使要求输出子串，只要同时保存开始索引即可。
可以使用两个指针进行处理，第一个指针作为开头，第二个指针统计不重复最大字符，然后记录当前长度，和保存的最大长度比较，如果超过最大长度则更新最大长度，如果没有重复字符，则第二个指针总是向后滑动，如果出现了重复的字符，则让第1个指针往后偏移，第二个指针保持不动，然后继续循环统计，走完全程即可。

为了加快查找重复字符的速度，可以建立一个Hash表来进行处理。

代码

迭代查找版

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.length())
            return 0;
 
        size_t max_sub_size = 0;
        size_t sub_size = 0;
        const char *first = s.c_str();
        const char *second = s.c_str();
        const char *three = s.c_str();
        bool is_exsit = false;
        
        do {
            is_exsit = false;
            three = second;
            while (three > first) {
                --three;
                if (*second == *three) {
                    is_exsit = true;
                    break;
                }
            }
            if (is_exsit) {
                ++first;
            } else {
                sub_size = second - first + 1;
                max_sub_size = sub_size > max_sub_size 
                    ? sub_size : max_sub_size;
                ++second;
            }
        } while (*second);
        return max_sub_size;
    }
};

Hash查找版

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (!s.length())
            return 0;
 
        size_t max_sub_size = 0;
        const char *first = s.c_str();
        const char *second = s.c_str();
        #define CHAT_MAX_SIZE (256)
        bool hash[CHAT_MAX_SIZE] = {0};
        #undef CHAT_MAX_SIZE
        
        #define MAX(_a, _b) ((_a) > (_b) ? (_a) : (_b))
        
        do {
            if (second > first && hash[*second]) {
                hash[*first] = false;
                ++first;
            } else {
                hash[*second] = true;
                max_sub_size = MAX(max_sub_size, second - first + 1);
                ++second;
            }
        } while (*second);
        return max_sub_size;
        #undef MAX
    }
};

*****