leetcode 链接：无重复字符的最长字串

题目

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

示例：

  1. 输入: s = "abcabcbb"
  2. 输出: 3 
  3. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

输入: s = ""
输出: 0

输入: s = " "
输出: 1

输入: s = "abba"
输出: 2

输入: s = "dvdf"
输出: 3

解答 & 代码

解法一：哈希map+滑动窗口

可用字符串 "dvdf" 过一遍流程

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 设置一个哈希表存储字符串 s 中出现过的字符及其最后出现的位置下标
        unordered_map<char, int> chaPosMap;
        int maxLen = 0;        // 无重复字符的最长子串长度
        int subStart = 0;    // 当前无重复字符子串的起始下标

        // 遍历字符串
        for(int i = 0; i < s.length(); ++i)
        {
            // 如果当前字符在哈希表中存在且位置下标大于等于 subStart，说明当前的子串出现重复字符了
            if(chaPosMap.find(s[i]) != chaPosMap.end() && chaPosMap[s[i]] >= subStart)
            {
                maxLen = (i - subStart) > maxLen ? (i - subStart) : maxLen;    // 更新最长子串长度
                subStart = chaPosMap[s[i]] + 1;    // 将子串起点移到重复字符之后
                chaPosMap[s[i]] = i;            // 将哈希表中当前字符对应的下标更新为 i
            }
            // 如果当前字符在哈希表中不存在
            else if(chaPosMap.find(s[i]) == chaPosMap.end())
            {
                chaPosMap.insert(make_pair(s[i], i));    // 将当前字符及其下标插入到哈希表
            }
            // 如果当前字符在哈下表中存在，但其位置下标小于等于 subStart，说明并不是重复字符，更新哈希表中的下标
            else
            {
                chaPosMap[s[i]] = i;
            }
        }
        // 注意最后更新一下 maxLen，否则如果字符串例如 " "，字符串遍历结束但未更新 maxLen 
        maxLen = (s.length() - subStart) > maxLen ? (s.length() - subStart) : maxLen;
        return maxLen;
    }
};

执行结果：

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 68.13% 的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了 66.41% 的用户

换一种写法：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int sLen = s.size();
        if(sLen <= 1)
            return sLen;

        int maxSubLen = 0;
        unordered_map<char, int> winMap;    // 哈希表，存储窗口中的字符及其出现的下标
        int left = 0, right = 0;            // 窗口的左右边界
        while(left < sLen || right < sLen)
        {
            // 如果右边界未越界，并且右边界的字符在窗口中不存在（哈希表中找不到，或找到了下标小于左边界）
            // 则窗口右边界右移
            while(right < sLen && 
                (winMap.find(s[right]) == winMap.end() || winMap[s[right]] < left))
            {
                winMap[s[right]] = right;
                ++right;
            }

            // 更新最长子串的长度
            if(right - left > maxSubLen)
                maxSubLen = right - left;

            if(right >= sLen)    // 若右边界越界，则停止滑动窗口，结束
                break;
            else                // 左边界跳到重复元素之后
                left = winMap[s[right]] + 1;
        }

        return maxSubLen;
    }
};

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 75.14% 的用户
内存消耗：8.2 MB, 在所有 C++ 提交中击败了 63.97% 的用户

解法二：哈希set+滑动窗口

上面的做法用空间换时间，哈希表中记录了字符的下标，因此当窗口右边界为重复值时，可从哈希表中查找到窗口中该重复值的位置，左边界直接跳到该位置后一个位置
也可以哈希表中只存字符，而不存键值对：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int sLen = s.size();
        if(sLen <= 1)
            return sLen;

        int maxSubLen = 0;
        unordered_set<char> winMap;        // 哈希表，存储窗口中出现过的字符
        winMap.insert(s[0]);
        int left = 0, right = 1;        // 左、右边界
        while(left < sLen)
        {
            // 右边界右移
            while(right < sLen && winMap.find(s[right]) == winMap.end())
            {
                winMap.insert(s[right]);
                ++right;
            }
            // 更新最长子串长度
            if(right - left > maxSubLen)
                maxSubLen = right - left;
            // 左边界右移
            winMap.erase(s[left]);
            ++left;
        }

        return maxSubLen;
    }
};

执行结果：

执行结果：通过

执行用时：28 ms, 在所有 C++ 提交中击败了 53.21% 的用户
内存消耗：10 MB, 在所有 C++ 提交中击败了 17.08% 的用户