当前位置:网站首页>LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二:编码实现
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二:编码实现
2022-08-03 09:06:00 【InfoQ】
欢迎访问我的GitHub
这里分类和汇总了欣宸的全部原创(含配套源码):
https://github.com/zq2599/blog_demos
- 本文是《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲》的第二篇,前一篇文章已经列出了完整的解题思路,今天来将此思路转化为具体的Java代码;
关键变量
- 编码之前先确定几个关键变量:
- 当前窗口中的元素都是不重复的,适合用一个HashSet来保存;
- max变量记录最长子串的长度;
- left表示窗口左侧相对整个字符串的位置,right表示窗口右侧相对整个字符串的位置,如下图:
代码实现
- 以下是代码,关键位置都有详细注释:
public class Solution1 {
public int lengthOfLongestSubstring(String s) {
//窗口的起始位置,窗口的结束为止,最长记录
int left = 0, right = 0, max = 0;
//表示窗口内有哪些值
Set<Character> set = new HashSet<>();
while (right < s.length()) {
//例如"abcdc",窗口内是"abcd",此时right等于[4],
//发现窗口内有array[right]的值,就缩减窗口左边,
//缩到窗内没有array[right]的值为止,
//当left一路变大,直到left=3的时候,窗口内已经没有array[right]的值了
if (set.contains(s.charAt(right))) {
//假如窗口内是"abc",当前是"c",那么下面的代码只会将"a"删除,left加一,再次循环
//而新一次循环依旧发现"c"还在set中,就再把"b"删除,left再加一...
set.remove(s.charAt(left++));
} else {
//窗口内没有array[right]的时候,就把array[right]的值放入set中,表示当前窗口内有哪些值
set.add(s.charAt(right++));
if ((right - left) > max) {
max = right - left;
}
}
}
return max;
}
public static void main(String[] args) {
System.out.println(new Solution1().lengthOfLongestSubstring("abcabcbb"));
}
}
- 上述代码的关键是set.remove(s.charAt(left++)),配合着外面的while循环,"left++"表示将窗口向右移动一个元素,并且将窗口中最左侧的元素从set中删除;
- 上述代码在LeetCode上提交成功,不过运行时间超过40ms,成绩并不理想,接下来的文章我们一起来做优化提升速度;
欢迎关注InfoQ:程序员欣宸
学习路上,你不孤单,欣宸原创一路相伴...
边栏推荐
- STP生成树(端口状态+端口角色+收敛机制 )|||| STP优化技术( uplinkfast技术+Portfast技术+backbonefast技术 )详解
- AcWing 3391. 今年的第几天?(简单题)
- 好用的插件
- Redis集群概念与搭建
- WPF 学习笔记《WPF样式基础》
- C# 一周入门高级编程之《C#-接口》Day Two
- 面渣逆袭:MySQL六十六问,两万字+五十图详解
- JMeter接口自动化发包与示例
- RViz报错: Error subscribing: Unable to load plugin for transport ‘compressed‘解决方法
- QT中线程调用GUI主线程控件的问题
猜你喜欢
随机推荐
swiper分类菜单双层效果demo(整理)
基于百度AI和QT的景物识别系统
【LeetCode】101.对称二叉树
STP生成树选举结果查看及验证
Validate floating point input
selenium IDE的3种下载安装方式
多媒体数据处理实验1:算术编码
English Grammar - Adverbial Clauses
flutter 应用 抓包
机器学习(公式推导与代码实现)--sklearn机器学习库
10分钟带你入门chrome(谷歌)浏览器插件开发
RViz报错: Error subscribing: Unable to load plugin for transport ‘compressed‘解决方法
别人都不知道的“好用”网站,让你的效率飞快
【字节面试】word2vector输出多少个类别
AcWing 3391. 今年的第几天?(简单题)
What are pseudo-classes and pseudo-elements?The difference between pseudo-classes and pseudo-elements
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二:编码实现
【网络安全】Kail操作系统
Add Modulo 10 (规律循环节,代码实现细节)
命令行加载特效 【cli-spinner.js】 实用教程