LeetCode #3:Longest Substring without Repeating Characters(无重复字符的最长子串)

题目描述

本题是滑动窗口的一道典型题,关键是要分析出可以使用滑动窗口来求解(左右指针不会回溯)、把握住滑动窗口左边界右移的条件。在本题中,当滑动窗口右边界遇到重复字符时,需要将左边界右移,直到左右边界区间的字串无重复字符。需要额外设置一个 hashmap 来记录每个字符的出现次数。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0; //左边界
        int r = 0; //右边界
        int n = s.length();
        unordered_map<char, int> flag;
        int res = 0;

        while(r < n) {
            flag[s[r]]++; //右边界的字符计数
            while(flag[s[r]] > 1) flag[s[l++]]--; //滑动窗口范围内有重复字母时,左边界右移直到无重复字符
            res = max(res, r - l + 1); //更新结果
            ++r; //右边界右移
        }

        return res;
    }
};

发表评论

您的电子邮箱地址不会被公开。