【算法】 滑动窗口—最长无重复子串
“无重复字符的最长子串”,难度为Medium,看下题目:
输入一个字符串 s,请计算 s 中不包含重复字符的最长子串长度。
比如,输入 s = "aabab",算法返回2,因为无重复的最长子串是 "ab" 或者 "ba",长度为2。
这道题终于有了点新意,不是一套框架就出答案,不过反而更简单了,稍微改一改框架就行了:
package SlidingWindow;
import java.util.HashMap;
import java.util.Map;
// leetcode 016 最长无重复子串
public class LNRS {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>(); // 记录窗口中的相应字符的出现次数
int left = 0, right = 0;
int res = 0; // 记录结果
while (right < s.length()) {
// c 是将要移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
window.put(c, window.getOrDefault(c, 0) + 1);
/*** debug 输出的位置***/
System.out.println("window:(" + left + ", " + right + ")");
/*********************/
// 判断左侧窗口是否要收缩
while (window.put(c, window.getOrDefault(c, 0)) > 1) { // window need shrink —窗口需要收缩
// d 是将要移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
window.put(d, window.getOrDefault(d, 0) - 1);
}
// 在这里更新答案
res = Math.max(res, right - left);
}
return res;
}
public static void main(String[] args) {
LNRS lnrs = new LNRS();
int res = lnrs.lengthOfLongestSubstring("aabab");
System.out.println(res);
}
}
连 need 和 valid 都不需要,而且更新窗口内数据也只需要简单更新计数器 window 即可。
当 window[c] 值大于1时,说明窗口中存在重复字符,不符合条件,就该移动 left 缩小窗口了。
唯一需要注意的是,在哪里更新结果 res 呢?我们要的是最长无重复子串,哪一个阶段可以保证窗口中的字符是没有重复的呢?这里和之前不一样,要在收缩窗口完成后更新 res,因为窗口收缩的 while 条件是存在重复元素,换句话说收缩完成后一定保证窗口中没有重复。