脚本宝典收集整理的这篇文章主要介绍了Leetcode刷题100天—3. 无重复字符的最长子串(滑动窗口+集合+双指针)—day21,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
作者:神的孩子在歌唱
大家好,我叫运智
难度中等6009收藏分享切换为英文接收动态反馈
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 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 * 104
s
由英文字母、数字、符号和空格组成package 滑动窗口;
import java.util.HashSet;
import java.util.Set;
public class _3_无重复字符的最长子串 {
// 集合+滑动窗口原理+双指针
public int lengthOfLongestSubstring(String s) {
// 通过右指针遍历字符到集合中,如果集合发现重复字符就退出循环,然后获取之前的长度,
// 在通过左指针慢慢取出之前在集合中的数,直到没有重复字符出现
// 定义左右指针left,right,和最大值ans
int ans=0,left=0,right=0;
// 定义集合
Set<Character> set=new HashSet<>();
// 第一层遍历左指针,取出集合中的数
int len=s.length();
for(;left<len;left++) {
// 如果left不为0,说明要么right到顶,要么存在相同元素,如果是第二种就不断移除
if (left!=0) {
// left左指针向左移动一格去除,因为之前++,left变成1,我们要移除第一个数,
// 若是下面遍历还发现有相同元素,left=2,在移除第一个数
set.remove(s.charAt(left-1));
}
// 通过右指针,将元素遍历到集合中,如果超过长度或者集合中已经存在该元素就停止
while(right<len&&!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
// 不断地移动右指针
right++;
}
if (right<len) {
ans=Math.max(ans, right-left);
}
// 通过比较每个窗口的长度来取最大值,窗口大小就是左指针减去右指针
ans=Math.max(ans, right-left);
}
return ans;
}
}
以上是脚本宝典为你收集整理的Leetcode刷题100天—3. 无重复字符的最长子串(滑动窗口+集合+双指针)—day21全部内容,希望文章能够帮你解决Leetcode刷题100天—3. 无重复字符的最长子串(滑动窗口+集合+双指针)—day21所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。