算法-滑动窗口

开始撸常用算法

理解滑动窗口

在嵌套循环中解决重复字符串或者区域内求最大和这种问题的时候，一般可以使用双循环来解决问题，但是使用滑动窗口可以单循环解决； 例如以上求连续无重复最大字符串长度，我们可以直接两个for循环进行记录比较一直到循环结束，但是如果用滑动窗口只需一次循环即可； 先确定左指针指向数组首位，并取元素i=0 此时窗口宽度为1，我们开始判断窗口是否能够扩大； 原窗口不包含B所以扩大，并将指针右移，此时窗口包含AB； 然后继续判断是否能扩大，判断是否能扩大可以理解为判断是否可以指针右移； 继续扩大； 此时，判断是否扩大，可以发现不能扩大，原窗口中含有B； 不能扩大的话，我们记录当前字符串，由题意可知是记录当前字符串长度，因为不能扩大，所以当前窗口满足不重复连续字符串条件； 并开始去掉窗口第一个元素，开始移动窗口，此时窗口为BC； 继续判断是否可以扩大窗口； 不可以扩大，记录当前窗口长度，因为当前窗口元素满足连续不重复字符串，并继续移动窗口； 然后以下同理； 窗口不含有元素C所以扩大； 继续判断； 此时指针到达末尾，指针右移判断的话超过数组长度，所以终结循环，记录当前窗口元素BCEF长度，即可得到最大长度为4；

算法实现

public int lengthOfLongestSubstring(String s) { //滑动窗口， 默认窗口为1 HashSet<Character> set =new HashSet<>(); int k=-1; int count=0; for (int i = 0; i < s.length(); i++) { if(i!=0){ set.remove(s.charAt(i-1)); } while (k+1<s.length()&&!set.contains(s.charAt(k+1))){ set.add(s.charAt(k+1)); k++; } count=Math.max(count,k-i+1); if(k+1>=s.length()) break; } return count; }