第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0003. 无重复字符的最长子串

题目地址(3. 无重复字符的最长子串)

题目描述

1
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
2
3
示例 1:
4
5
输入: "abcabcbb"
6
输出: 3
7
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
8
示例 2:
9
10
输入: "bbbbb"
11
输出: 1
12
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
13
示例 3:
14
15
输入: "pwwkew"
16
输出: 3
17
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
18
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
Copied!

前置知识

公司

  • 阿里
  • 字节
  • 腾讯

思路

题目要求连续, 我们考虑使用滑动窗口。 而这道题就是窗口大小不固定的滑动窗口题目,然后让我们求满足条件的窗口大小的最大值,这是一种非常常见的滑动窗口题目。
算法:
用一个 hashmap 来建立字符和其出现位置之间的映射。同时维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。
  1. 1.
    如果当前遍历到的字符从未出现过,那么直接扩大右边界;
  2. 2.
    如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符;
  3. 3.
    重复(1)(2),直到窗口内无重复元素;
  4. 4.
    维护一个全局最大窗口 res,每次用出现过的窗口大小来更新结果 res,最后返回 res 获取结果;
  5. 5.
    最后返回 res 即可;
3.longestSubstringWithoutRepeatingCharacters

关键点

  • mapper 记录出现过并且没有被删除的字符
  • 滑动窗口记录当前 index 开始的最大的不重复的字符序列

代码

代码支持:C++,Java,Python3
C++ Code:
1
class Solution {
2
public:
3
int lengthOfLongestSubstring(string s) {
4
5
int ans = 0, start = 0;
6
int n = s.length();
7
//
8
map<char, int> mp;
9
10
for(int i=0;i<n;i++)
11
{
12
char alpha = s[i];
13
if(mp.count(alpha))
14
{
15
start = max(start, mp[alpha]+1);
16
}
17
ans = max(ans, i-start+1);
18
// 字符位置
19
mp[alpha] = i;
20
}
21
22
return ans;
23
}
24
};
Copied!
Java Code:
1
class Solution {
2
public int lengthOfLongestSubstring(String s) {
3
int ans = 0, start = 0;
4
int n = s.length();
5
//
6
Map<Character, Integer> map = new HashMap<>();
7
8
for(int i=0;i<n;i++)
9
{
10
char alpha = s.charAt(i);
11
if(map.containsKey(alpha))
12
{
13
start = Math.max(start, map.get(alpha)+1);
14
}
15
ans = Math.max(ans, i-start+1);
16
// 字符位置
17
map.put(alpha, i);
18
}
19
20
return ans;
21
}
22
}
Copied!
Python3 Code:
1
from collections import defaultdict
2
3
4
class Solution:
5
def lengthOfLongestSubstring(self, s: str) -> int:
6
l = 0
7
ans = 0
8
counter = defaultdict(lambda: 0)
9
10
for r in range(len(s)):
11
while counter.get(s[r], 0) != 0:
12
counter[s[l]] = counter.get(s[l], 0) - 1
13
l += 1
14
counter[s[r]] += 1
15
ans = max(ans, r - l + 1)
16
17
return ans
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。