当前位置:首页 » 《随便一记》 » 正文

Leetcode刷题100天—3. 无重复字符的最长子串(滑动窗口+集合+双指针)—day21_智的博客

4 人参与  2021年11月06日 09:43  分类 : 《随便一记》  评论

点击全文阅读


前言:

作者:神的孩子在歌唱

大家好,我叫运智

image-20210828220024172

3. 无重复字符的最长子串

难度中等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;
    }
}

本人csdn博客:https://blog.csdn.net/weixin_46654114

转载说明:跟我说明,务必注明来源,附带本人博客连接。


点击全文阅读


本文链接:http://zhangshiyu.com/post/30527.html

指针  字符  长子  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 男友霸道给我开黑卡,转头却骂我是捞女最新章节_肖年顾客黑卡热文_小说后续在线阅读_无删减免费完结_
  • 他在回忆尽头全集_贺南舟许清梨叶絮完结txt_小说后续在线阅读_无删减免费完结_
  • 旅游结婚那天未婚夫另娶女秘书,我让他们一无所有连载_老公迎宾超长版_小说后续在线阅读_无删减免费完结_
  • 完结文异界修仙我的直播间能打赏核弹列表_完结文异界修仙我的直播间能打赏核弹(江流年沈红菱)
  • 全书浏览陪弟弟混骑行圈,离婚你哭什么?(韩星河柳千雪)_陪弟弟混骑行圈,离婚你哭什么?(韩星河柳千雪)全书结局
  • 老公出轨我助攻虐心反转_秦绍卿卿阿溪后续加长_小说后续在线阅读_无删减免费完结_
  • 替老婆坐牢出狱那天,我被送去斗兽场精校文本_许言沈宇郑子番茄热门_小说后续在线阅读_无删减免费完结_
  • 沐巍澜温溪:结局+番外(爱如一刹花火)电子书畅享阅读无广告
  • 傅凌川林柚续集(傅凌川林柚)章节前文+全书阅读(替嫁燃婚:小祖宗嘴硬腰软)最新连载
  • 资助生把导盲犬做成火锅后,我家杀疯了!列表_资助生把导盲犬做成火锅后,我家杀疯了!(陈米雪波波)
  • 沈瑾钰林沐橙豪门废妻浴火复仇续集(豪门废妻浴火复仇)章节在线阅读最近章节
  • 明明图分手费,我怎么就入赘了?(顾池柳如烟),明明图分手费,我怎么就入赘了?

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1