LeetCode3. 无重复字符的最长子串
LeetCode3. 无重复字符的最长子串
Yuyy
发布于 2022-06-28 20:18:18
发布于 2022-06-28 20:18:18
代码可运行
运行总次数：0
代码可运行
本文最后更新于 507 天前，其中的信息可能已经有所发展或是发生改变。
一、思路
这题也是滑动窗口类型，判断窗口内是否有重复值时，我使用的是集合+队列。集合判断是否重复，队列记录窗口位置。解题后看了下题解，才发现滑动窗口类型确实做少了，这题明明可以用通用解法：下标+map，下标记录窗口位置，map判断是否重复（泛型为<字符，出现的次数>）。
用集合+队列还有个坑：当窗口从未缩小时，是没有触发计算length，需要在返回结果时做处理。
二、题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。示例 4:
输入: s = ""
输出: 0提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
Related Topics
- 哈希表
- 双指针
- 字符串
- Sliding Window
\n
- 👍 4922
- 👎 0
三、代码
public int lengthOfLongestSubstring(String s) {
Queue<Character> queue = new LinkedList<>();
HashSet<Character> set = new HashSet<>();
int left = 0;
int right = 0;
int length = 0;
while (s.length() > right) {
char c = s.charAt(right);
if (set.contains(c)) {
length = right - left > length ? right - left : length;
right++;
queue.add(c);
char c1 = queue.poll();
left++;
while (c1 != c) {
set.remove(c1);
c1 = queue.poll();
left++;
}
} else {
set.add(c);
queue.add(c);
right++;
}
}
return right - left > length ? right - left : length;
}Post Views: 309
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-2-05 1，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
