Q3：Longest Substring Without Repeating Characters
2024-10-08 17:34:14
3. Longest Substring Without Repeating Characters
官方的链接：3. Longest Substring Without Repeating Characters
Description ：
Given a string, find the length of the longest substring without repeating characters.
Example:
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.
问题描述
给定一个字符串，找出最长不重复子串的长度
思路
建立一个128的数组，存储字符的下标，min存储非重复子串的最小下标，max存储最大下标。max逐步加大，如果下一个字符的下标大于min，则增加min，同时记录最大的max - min + 1
public class Q3_LongestSubstringWithoutRepeatingCharacters {
public int lengthOfLongestSubstring(String s) {
if (null == s || s.length() < 1) {
return 0;
}
// 初始化128的数组，足够存储所有字符
int[] intArray = new int[128];
for (int i = 0; i < intArray.length; i++) {
intArray[i] = -1;
}
char num = s.charAt(0);
intArray[num] = 0;
int min = 0;
int max = 0;
int count = 1;
for (int i = 1; i < s.length(); i++) {
num = s.charAt(i);
max = i;
if (intArray[num] == (max - 1)) {
count = max - min > count ? max - min : count;
min = max;
} else if (intArray[num] >= min) {
count = max - intArray[num] > count ? max - intArray[num] : count;
min = intArray[num] + 1;
} else {
count = max - min + 1 > count ? max - min + 1 : count;
}
intArray[num] = i;
}
return count;
}
public static void main(String[] args) {
Q3_LongestSubstringWithoutRepeatingCharacters longest = new Q3_LongestSubstringWithoutRepeatingCharacters();
System.out.println(longest.lengthOfLongestSubstring("nfpdmpi"));
}
}
最新文章
- ASP.NET Core MVC 在linux上的创建及发布
- H5中的touch事件
- 使用js设置input标签只读 readonly 属性
- [转]Installing python 2.7 on centos 6.3. Follow this sequence exactly for centos machine only
- Keepalived 配置实例
- js 小数[非]四舍五入
- javascript 漏洞
- HDU 1724 Ellipse（数值积分の辛普森公式）
- IIS7下,flush无效,解决方案
- Android Touch(2)View.OnTouchEvent与View.OnTouchListener区别
- uva331 - Mapping the Swaps
- Quality Center配置邮箱服务
- <转>一个最不可思议的MySQL死锁分析
- android4.0 的图库Gallery2代码分析(一)
- Eclipse中应用的调试
- Java中四种遍历List的方法
- VS2015 安装nuget离线包nupkg文件
- Ant Design按需加载
- pygame 游戏舞台搭建典型应用
- EOS智能合约开发(四)：智能合约部署及调试(附编程示例)