滑动窗口 | Java | (hot100) 力扣 3

力扣 3.无重复字符的最长子串

暴力法：双层for循环，i-j的字符查重

滑动窗口：因为这题被分在这个类别里，那么已知要用滑动窗口，思路应该是什么。

反正我想不出来……

• 看了别人的题解写出来的
• 出错点：特别容易下标和元素弄混

class Solution {public int lengthOfLongestSubstring(String s) {Set<Character>set = new HashSet<Character>();char ch;int res=0;for(int left=0,right=0; right<s.length(); right++) {ch = s.charAt(right);while(set.contains(ch)) {set.remove(s.charAt(left)); //注意这里是用leftleft++;}set.add(ch);res = Math.max(res, right-left+1);}return res;}
}

ACM模式练习 https://www.acwing.com/problem/content/57/

滑动窗口模板

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {//当前考虑的元素while (l <= r && check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意，统计相关信息
}

本题变形

腾讯面试题，需要返回的是子串（来自力扣评论）

我的思路：在这一句下功夫：res = Math.max(res, right-left+1);
多设置一个变量 strLeft，当更新res的时候，strLeft = left。当for循环结束，知道子串长度res和字串起始值strLeft就可以返回字串了

public class Collection01 {public static void main(String[] args) {lengthOfLongestSubstring("pwwkew");}public static int lengthOfLongestSubstring(String s) {Set<Character>set = new HashSet<Character>();char ch;int res=0;int strleft=0;for(int left=0,right=0; right<s.length(); right++) {ch = s.charAt(right);while(set.contains(ch)) {set.remove(s.charAt(left)); //注意这里是用leftleft++;}set.add(ch);if((right-left+1)>res) {res = right-left+1;strleft = left;}}System.out.println(res);System.out.println(strleft);System.out.println(s.substring(strleft,strleft+res));return res;}}