LeetCode热题100(七)—— 3.无重复字符的最长子串
LeetCode热题100(七)—— 3.无重复字符的最长子串
- 题目描述
- 代码实现
- 思路解析
- 你好,我是杨十一,一名热爱健身的程序员
- 在Coding的征程中,不断探索与成长
- LeetCode热题100——刷题记录(不定期更新)
此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
愿与诸君共同探讨,在代码世界里携手共进,攻克难题,提升自我
题目描述
给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) return s.length();
int L = 0;
int R = 1;
int maxLen = 1;
Set<Character> set = new HashSet<>();
set.add(s.charAt(0));
while (R < s.length()) {
char ch = s.charAt(R);
if (set.contains(ch)) {
maxLen = Math.max(maxLen, R - L);
set.remove(ch);
while (s.charAt(L) != ch) {
set.remove(s.charAt(L++));
};
set.remove(s.charAt(L++));
}
set.add(s.charAt(R));
R++;
}
return Math.max(maxLen, R - L);
}
}
思路解析
- 输入:字符串
- 输出:最长不重复子串的长度
- 思路:双指针 + 哈希集合
- 子串长度:双指针固定左指针,右指针右移直到出现重复字符串
- 重复判断:哈希集合存储子串字符,判断右指针移动下一个位置的字符是否重复
- 如果重复:
- 记录当前
[L,R)
之间的子串长度,并判断是否是最大子串长度 - 左指针
L
右移直至子串中重复字符的下一个位置,作为新的子串起点
- 记录当前
- 时间复杂度:
O
(
n
)
O(n)
O(n)
- 左指针和右指针各遍历字符串一次 O ( 2 n ) = O ( n ) O(2n) =O(n) O(2n)=O(n)
- 虽然是双层循环,但不是 n 2 n^2 n2
L
或R
指针移动时,另外一个指针固定不移动,并非R或L每移动1次,另一个指针就遍历一遍
- 空间复杂度:
O
(
n
)
O(n)
O(n),也有解释是
O
(
∣
Σ
∣
)
O(|\Sigma|)
O(∣Σ∣)
- 区别在于重复字符是否算作同一个空间。如上,字符
c
出现2次,哈希集合删除后再添加算作使用了2个空间,两个指针遍历字符串,所有字符都会添加进哈希集合中(部分会在过程中删除) - 官方解释:其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在 [0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有 ∣Σ∣ 个,因此空间复杂度为 O(∣Σ∣)
- 区别在于重复字符是否算作同一个空间。如上,字符
- 你好,我是杨十一,一名热爱健身的程序员
- 在Coding的征程中,不断探索与成长
- LeetCode热题100——刷题记录(不定期更新)
此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
愿与诸君共同探讨,在代码世界里携手共进,攻克难题,提升自我
原文地址:https://blog.csdn.net/Young_4/article/details/145380852
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/522375.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/522375.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!