游仙建设局官方网站,wordpress 左侧边栏,做的比较早的海淘网站,网页制作软件中的三剑客“无重复字符的最长子串”#xff0c;难度为Medium#xff0c;看下题目#xff1a; 输入一个字符串 s#xff0c;请计算 s 中不包含重复字符的最长子串长度。 比如#xff0c;输入 s aabab#xff0c;算法返回2#xff0c;因为无重复的最长子串是 ab… “无重复字符的最长子串”难度为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) {MapCharacter, 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 条件是存在重复元素换句话说收缩完成后一定保证窗口中没有重复。
