窗口法总结

yPhantom 2019年10月26日 43次浏览

前言

窗口法(sliding window)是面试当中的高频题,主要考虑指针变化以及窗口移动的条件。然而由于细节比较多,经常出现有思路却写不出的情况,在本篇文章中尝试对大部分的窗口法题目做一个总结,提取一个或者多个模板。强化记忆。

窗口法的题目的核心思想其实就是双指针的移动,这类题目常见于字符串或者数组。且题型很多,条件各式各样,不总结的话容易被表面迷惑,实际上抽丝剥茧下来还是那么个框架。

这种题一般都是基于字符串或者数组的,并且要仔细审题,有时候窗口大小固定,这时候left指针和right指针同步增加,比如480. SLIDING WINDOW MEDIAN,求固定k窗口大小的的中位数。而对于窗口大小不固定的题目,一般都是求最大的或者最小的满足某种条件的字符串或者数组长度。

而且,这种题目都和数字或者字符出现的次数有关。并且,按我之前解的经验来看,字符串类型的题目的就用一个保存128位ASCII字符的数组或者26位字母的数组来存频次,数字类型的可以用hashmap,hashset这样的。

题型一

关键字:最、连续、长度。

这类题呢一般都是给我们一个字符串,求这个字符串中连续的满足某个条件的最长或者最短子字符串。(或者求长度,或者求满足条件的所有字符串或者其个数)。

假设输入为字符串s,上来先是一套组合拳

// 1. 存字符串的长度
int n = s.length();
// 2. 一般情况下所有字符,那就是128个,看情况
int[] count = new int[128];
// 3. 定义左指针
int left = 0;
// 4. 定义返回值,可能是int,也可能是个list等数据结构
int res = 0;