leetcode 03.md

leetcode 03

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

示例 1:

输入: "abcabcbb"

输出: 3

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

示例 2:

输入: "bbbbb"

输出: 1

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

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

方法：哈希表 + 滑动窗口

哈希表同于建立从char->int的映射，当然这个映射用数组也是可以的，只不过哈希表更方便判断元素在表中的位置map.count(key);

而数组判断元素在不在其中就得用vector.find(vector.begin(), vector.end(), key);

并且如果有中文的话那还是用哈希表做映射适用范围会更广。

昨天面试就是这个，面试官说有中文呢，我就没想到用哈希表。

思路

1. 如果当前遍历到的字符从未出现过，那么直接扩大右边界；

2. 如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；

3. 重复（1）（2），直到窗口内无重复元素；

4. 维护一个全局最大窗口 ret，每次用出现过的窗口大小来更新结果 ret，最后返回 ret 获取结果;

5. 最后返回 ret 即可;

int lengthOfLongestSubstring(string s) {
        int ret = 0, l = 0;
        vector<char> m;
        for (int i = 0; i < s.length(); i++) {
            char ch = s[i];
            if (m.count(ch)) l = max(l, m[ch] + 1);
            ret = max(ret, i - l + 1);
            m[ch] = i;
        }
        return ret;
    }