3. 无重复字符的最长子串
程序员文章站
2024-02-25 09:49:34
...
题目
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 无重复字符的最长子串是 “abc”,其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 无重复字符的最长子串是 “b”,其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 无重复字符的最长子串是 “wke”,其长度为 3。
请注意,答案必须是一个子串,“pwke” 是一个子序列 而不是子串。
方法: 采用滑动窗口,遍历一遍求解
/**
* 就是从头开始产生一个划窗,没遇到重复的窗体右边界加1,统计窗体大小,
* 遇到重复的后,窗体的左边界就移动到前面那个重复元素的下一个
* 表示在两个重复元素间最大子串已经知道了,应该开始从前面重复元素的下一个字符开始了
*/
public static int maxNoSubstring(String s) {
int i=0,j=0,ans=0;
int n = s.length();//方法型的获取长度的单独计算,避免在for循环中多次计算
HashMap<Character,Integer> map = new HashMap<>();//使用map装每个字符的位置的下一个
for(;j<n;j++) {
Character key = new Character(s.charAt(j));
if(map.containsKey(key)) {
i = Math.max(map.get(s.charAt(j)), i);//大于等于i的新的重复元素的起始位置
}
ans = Math.max(ans, j-i+1);//获取新子串和就的最大子串的最长的长度
map.put(key, j+1);//将新的元素记录其位置的下一个,或者用新的位置替换已有的元素
}
return ans;
}
```