剑指offer48 最长不重复字符的子字符串【哈希表、双指针】

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • s.length <= 40000

解题思路

方法一:双指针+哈希表(Map)

​ 利用双指针加哈希表的方法,哈希表记录最近一次字符的下标,一轮遍历字符串,当发现字符已经出现过,则

  1. 计算从left到当前的字符串长度;
  2. 设置left指针至(前一个出现的位置 和 left原先指向的位置)的最大值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0){
return 0;
}
int len = s.length();
int ans = 0;
int left = 0;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
ans = Math.max(ans, i - left);
left = Math.max(map.get(c) + 1, left);
}
map.put(c,i);
}
ans = Math.max(ans, len - left);
return ans;
}
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1), 字符的 ASCII 码范围为 0 ~ 127,所以map最多存放128个键值对,O(128).

方法二:双指针+哈希表(数组)

字符的 ASCII 码范围为 0 ~ 127,所以直接申请128空间的int数组来记录字符的下标

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int ans = 0;
int left = 0;
int[] last = new int[128];
int f = s.charAt(0);
for (int i = 1; i < len; i++) {
int c = s.charAt(i);
if (last[c] != 0 || c == f) {
ans = Math.max(ans, i - left);
left = Math.max(last[c] + 1, left);
}
last[c] = i;
}
ans = Math.max(ans, len - left);
return ans;
}
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

资源

剑指offer48 最长不重复字符的子字符串【哈希表、双指针】

http://example.com/2021/05/28/剑指offer48-最长不重复字符的子字符串/

Author

John Doe

Posted on

2021-05-28

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.