| by YoungTimes | No comments

面试刷题-滑动窗口-无重复字符的最长子串

题目-无重复字符的最长子串

链接: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

步骤一。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤二。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤三。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤四。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤五。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤六。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
步骤七。来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/

我们可以使用「滑动窗口」来解决这个问题,使用两个指针表示字符串中某个子串的左右边界。在每一步操作中,我们将左指针向右移动一格,表示子串的起始位置,然后不断的向右移动右指针,但要保证这两个指针对应的子串没有重复的字符。如果出现重复的字符,将左指针移动到首个不重复的字符,如此重复,直到得到所有最长不重复字符的子串长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        std::unordered_set<char> char_set;
        int left = 0;
        int ans = 0;

        for (int i = 0; i < s.length(); i++) {
            while (char_set.count(s.at(i)) > 0) {
                char_set.erase(s.at(left));
                ++left;
            }

            ans = std::max(ans, i - left + 1);
            char_set.insert(s.at(i));
        }

        return ans;
    }
};

除非注明,否则均为[半杯茶的小酒杯]原创文章,转载必须以链接形式标明本文链接

本文链接:http://www.banbeichadexiaojiubei.com/index.php/2020/12/27/%e9%9d%a2%e8%af%95%e5%88%b7%e9%a2%98-%e6%bb%91%e5%8a%a8%e7%aa%97%e5%8f%a3-%e6%97%a0%e9%87%8d%e5%a4%8d%e5%ad%97%e7%ac%a6%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e4%b8%b2/