滑动窗口-3. 无重复字符的最长子串

文章目录1.题解核心解题思路滑动窗口1. 题目要求2. 核心思想滑动窗口双指针3. 执行流程你代码的逻辑4. 一句话总结2.机考代码3.知识点讲解1.本题所用到的String方法1.charAt(int index)2.length()2.List.contains()HashSet.contains()力扣地址 中等3. 无重复字符的最长子串1.题解核心解题思路滑动窗口我用最简单、最容易记住的方式讲面试口述也能直接用1. 题目要求给你一个字符串找到无重复字符的最长子串的长度。2. 核心思想滑动窗口双指针你可以把字符串想象成一条滑动的窗口右指针r负责扩张不断往右走把字符加入窗口左指针l负责收缩一旦发现重复就把左边的字符移出窗口Set负责记录窗口里有哪些字符快速判断是否重复3. 执行流程你代码的逻辑右指针r遍历每个字符如果字符没出现过加入集合更新最大长度r右移如果字符已经出现过不断把左指针l向右移删除重复字符直到窗口里没有当前字符再把新字符加进来r继续右移最终maxLen就是答案4. 一句话总结用左右指针维护一个无重复的窗口右扩左缩记录窗口最大长度。classSolution{publicintlengthOfLongestSubstring(Strings){intl0,r0;intmaxLen0;SetCharactersetnewHashSet();while(rs.length()){charcs.charAt(r);if(!set.contains(c)){set.add(c);maxLenMath.max(maxLen,r-l1);r;}else{while(set.contains(c)){set.remove(s.charAt(l));l;}set.add(c);r;}}returnmaxLen;}}2.机考代码packagec_huadongchuangkou;importjava.util.HashSet;importjava.util.Scanner;importjava.util.Set;publicclassMain{publicstaticintlengthOfLongestSubstring(Strings){intl0,r0;intmaxLen0;SetCharactersetnewHashSet();while(rs.length()){charcs.charAt(r);if(!set.contains(c)){set.add(c);maxLenMath.max(maxLen,r-l1);r;}else{while(set.contains(c)){set.remove(s.charAt(l));l;}set.add(c);r;}}returnmaxLen;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 输入一行字符串Stringssc.nextLine();// 输出答案System.out.println(lengthOfLongestSubstring(s));}}3.知识点讲解1.本题所用到的String方法1.charAt(int index)作用返回字符串指定索引处的字符。2.length()作用返回字符串的长度。2.List.contains()HashSet.contains()List.contains() 遍历查找 →O(n)HashSet.contains() 哈希定位 →O(1)所以滑动窗口必须用 Set/Map不能用 List。