滑动窗口算法—最长无重复子串

        “无重复字符的最长子串”，难度为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 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复。