最长子串(Leetcode-3 Longest Substring Without Repeating Characters)
2024-08-25 23:51:04
Question:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
问题描述:
给一个字符串,找出这个字符串的无重复字符的最长子串的长度。
实例:
1,“abcabcbb”的最长子串是“abc”,长度为3。
2,“bbbbb”的最长子串是“b”,长度为1。
3,“pwwkew”的最长子串是“wke”,长度为3。
解题思路:
这个题的关键在于重复的字符!
一个子串不可能出现重复的字符,那么我们可以用两个指针,一个指针用来遍历字符串,两个指针之间保持无重复字符,那么两个指针之间的长度即最大子串的长度。当发现有重复的字符时,另一个指针指向这个字符上一次出现的位置的下一个字符,继续遍历,直到找到最长子串。
代码示例:
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
最新文章
- [Erlang 0109] From Elixir to Erlang Code
- Autofac 的构造函数注入方式
- IOS开发之—— 客服QQ(调用qq网页聊天),客服热线(拨打电话)
- linux tricks 之 container_of.
- RFID第二次作业
- 关于.NET邮件的收发问题总结
- 下拉选择框加listview删除
- 升级iOS10后SearchController焦点无法获取的问题
- 使用Spring MVC 的表单控制器SimpleFormController
- QML之TextEdit
- 【转】java jawin api 中文 invoke方法
- Preemption Context Switches 和 Synchronization Context Switches
- avalon组件
- IOS开发之路三(XML解析之GDataXML的使用)
- SuperSocket 最基础入门
- Akamai CDN
- 聊一聊JS的原型链之高级篇
- 第n次搭建 SSM 框架
- C# 初识Redis
- LeetCode--035--搜索插入位置(java)