0%

最长不重复子串的有趣解法

发表于 更新于 分类于 阅读次数：
本文字数： 1.3k 阅读时长 ≈ 2 分钟

最长不重复子串是leetcode一道经典的题目，要求找出一个字符串中最长不重复子串的长度

首先清楚一个概念，子串是连续的字符组成的，子序列是不连续的字符组成的。

常规做法

一种常规的想法就是以每个字符作为起始点，查找以这个字符开始的最长子串，然后输出最大的长度，这种做法需要两层循环，第一层循环是起始字符 s[i]，第二层循环是以第一层起始字符后的第一个字符开始 s[j]，如果 s[j] 出现在子串 s[i, j] 中，则以 s[i] 开头的最长不重复子串长度就是 j - i。这种做法比较耗时，因为涉及了大量的重复比较。

滑动窗口法

有一种巧妙的方法就是滑动窗口，一般也称为双指针方法，两个指针分别表示窗口的两边。

滑动窗口法的思想是一层循环，每次循环找到以这个字符为结尾的子串，具体做法就是：

  • 外层循环遍历所有字符，初始化窗口两边都为 0，建立一个 hashmap 用于记录当前窗口字符出现次数。
  • 如果当前字符在 hashmap 中已经出现，说明窗口中包含了这个字符，因此将窗口左边逐一向右，并依次减少其 hashmap 出现的次数（因为已经不在窗口中了），直到所有字符出现次数都为 1，说明没有重复了。
    • 这里有一个技巧，就是窗口右边字符出现次数不为 1 的时候我们开始移动左边窗口，这个时候，窗口内只有一个重复元素，就是右边窗口所在的字符，我们需要将左边窗口移动到重复元素之后的第一个字符上，这样左边窗口到右边窗口的子串就不会有重复元素了。
    • 这个地方其实也有一次小循环，但是相比第一种方法，减少了重复比较的次数。
  • 如果当前字符没有出现过，则以当前右边窗口所在字符为结尾的不重复子串就是窗口的长度。判断当前长度和已有记录长度，选择最大长度，右边窗口继续右移，考察下一个字符。
    • 这个地方也有一个技巧，就是当前字符的左边窗口边界一定是前一字符左边窗口边界及其之后，因为前一字符的左边窗口是其重复字符后的第一个字符，而当前字符包含了前一字符，因为其左边界不可能位于前一字符左边界的前面。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
    }
};

总结

在解这道题的时候我想到的是，其实很多时候都需要拥有这种以该字符作为结尾这种逆向思维的方式，往往能找到比较有效的方法。