3. 无重复字符的最长子串【双指针】
2022/4/13 6:23:06
本文主要是介绍3. 无重复字符的最长子串【双指针】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
难度:中等
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成
题解
利用双指针原理(队列)
- 左指针按兵不动,右指针一直右移,我们需要检测的区间是是【l,r】区间的字符串
- 每一次移动都要将元素放入hash表中前,但是在放入先检测该元素是否存在
- 如果存在,则需要更新左指针的位置,这里需要注意的是,可能左指针的位置比需要更新的位置更靠后,也就是说,需要的更新的位置是已经舍弃的区间,那么就比较两端区间的位置谁更大即可
- 如果asc表能容纳所有目标字符的话,用asc表更快,但是hash容纳量更大
class Solution { public int lengthOfLongestSubstring(String s) { // 特殊情况直接返回 if (s.length() < 2) { return s.length(); } int max = 1; HashMap<Character, Integer> hashMap = new HashMap<>(); int l = 0, r = 0; char[] chars = s.toCharArray(); while (r < chars.length) { // 如果元素存在,那么比较更新位置,因为有可能右指针的元素之前插入过,但是被更新区间的时候舍弃了,所以需要确定是否被舍弃,也就是该元素是否在左指针之前 if (hashMap.containsKey(chars[r])) { l = Math.max(l,hashMap.get(chars[r])+1); } // 更新元素 hashMap.put(chars[r], r); // 更新最长子串 max = Math.max(max, r - l + 1); r++; } return max; } }
- 2022年4月12日23:52:57
这篇关于3. 无重复字符的最长子串【双指针】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?