最长不重复子串是leetcode一道经典的题目,要求找出一个字符串中最长不重复子串的长度
首先清楚一个概念,子串是连续的字符组成的,子序列是不连续的字符组成的。
一种常规的想法就是以每个字符作为起始点,查找以这个字符开始的最长子串,然后输出最大的长度,这种做法需要两层循环,第一层循环是起始字符 s[i]
,第二层循环是以第一层起始字符后的第一个字符开始 s[j]
,如果 s[j]
出现在子串 s[i, j]
中,则以 s[i]
开头的最长不重复子串长度就是 j - i
。这种做法比较耗时,因为涉及了大量的重复比较。
有一种巧妙的方法就是滑动窗口,一般也称为双指针方法,两个指针分别表示窗口的两边。
滑动窗口法的思想是一层循环,每次循环找到以这个字符为结尾的子串,具体做法就是:
- 这里有一个技巧,就是窗口右边字符出现次数不为 1 的时候我们开始移动左边窗口,这个时候,窗口内只有一个重复元素,就是右边窗口所在的字符,我们需要将左边窗口移动到重复元素之后的第一个字符上,这样左边窗口到右边窗口的子串就不会有重复元素了。
- 这个地方其实也有一次小循环,但是相比第一种方法,减少了重复比较的次数。
- 这个地方也有一个技巧,就是当前字符的左边窗口边界一定是前一字符左边窗口边界及其之后,因为前一字符的左边窗口是其重复字符后的第一个字符,而当前字符包含了前一字符,因为其左边界不可能位于前一字符左边界的前面。
代码如下:
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int n = s.size();
if (n == 0)
return 0;
unordered_map<char, int> m;
int left = 0, len = 0;
for (int i = 0; i < n; i++)
{
m[s[i]]++;
while (m[s[i]] > 1)
{
m[s[left++]]--;
}
len = max(len, i - left + 1);
}
return len;
}
};
在解这道题的时候我想到的是,其实很多时候都需要拥有这种以该字符作为结尾这种逆向思维的方式,往往能找到比较有效的方法。
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。