算法

无重复字符的最长子串

字数: 514

经典力扣第三题(😭)。
滑动窗口+哈希表很好写(虽然我第一次没写出来💩)。

题目

力扣：3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

题解

滑动窗口+哈希表

该子串问题，很显然发现是单调的，也就是指针不会后退。要满足无重复字符可以用哈希表存储进行判断。
显然，用 left 和 right 双指针“框住”窗口。可知：
如果(left, right) 不存在重复字符串，则 right 右移以取得更长的子串。若存在重复字符，因为所求的子串是连续的，所以右移 left 缩小窗口。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
  public:
    int lengthOfLongestSubstring(std::string s)
    {
        int answer = 0;
        std::unordered_map<char, int> char_map;
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            char_map[s[right]]++;
            while (char_map[s[right]] > 1)
            {
                char_map[s[left]]--;
                left++;
            }
            answer = std::max(answer, right - left + 1);
        }
        return answer;
    }
};

判断子串重复使用 char_map[s[right]] > 1 即可很好判断，通过循环该条件不断右移 left 指针即可再次得到新的目标子串。
这样的算法时间复杂度是 $O(n)$

类似题

和本题大体一样的滑动窗口题有：

209. 长度最小的子数组

 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

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

class Solution
{
  public:
    int minSubArrayLen(int target, std::vector<int> &nums)
    {
        int ans = INT_MAX;
        int sum = 0;
        for (int left = 0, right = 0; right < nums.size(); right++)
        {
            sum += nums[right];
            while (sum >= target && left <= right)
            {
                ans = std::min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

同样两个状态，用 while 循环得到目标子串。

参考资料

  1. bilibili 掌握滑动窗口本质，秒杀相关题型