滑动窗口
滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作，它的原理与网络传输TCP协议中的滑动窗口协议（Sliding Window Protocol）基本一致。
这种技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。滑动窗口主要应用在数组和字符串上。
例如，设定滑动窗口（window）大小为 3，当滑动窗口每次划过数组时，计算当前滑动窗口中元素的和，可以得到一组结果 res。
因为滑动窗口是靠窗口起始、结束两个位置来表示的，所以滑动窗口也可以看作特殊的“双指针”。双指针法
例题
滑动窗口最大值（#239）
堆
构建一个大顶堆（Max Heap），那么堆顶元素 heap[0] 永远是最大的。每次移动窗口的时候，我们只要维护这个堆、在里面插入删除元素，然后返回堆顶元素heap[0]就可以了。
在代码中，我们可以用一个优先队列（Priority Queue）来实现大顶堆
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
// 用优先队列定义一个大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < k; i++) {
maxHeap.add(nums[i]);
}
result[0] = maxHeap.peek();
// 遍历数组
for(int i = 1; i <= nums.length - k; i++){
maxHeap.remove(nums[i - 1]);
maxHeap.add(nums[i + k - 1]);
result[i] = maxHeap.peek();
}
return result;
}
- 时间复杂度： O(Nlog(k))，在大小为 k 的堆中插入一个元素只需要消耗 log(k) 时间，因此这样改进后，算法的时间复杂度为O(Nlog(k))。但提交依然会超出时间限制。
- 空间复杂度：O(N)，输出数组用到了O(N-k+1)的空间，大顶堆用了O(k)
双向队列
我们发现，窗口在滑动过程中，其实数据发生的变化很小：只有第一个元素被删除、后面又新增一个元素，中间的大量元素是不变的。也就是说，前后两个窗口中，有大量数据是 重叠 的。
[1, 3, -1,] -3, 5, 3, 6, 7
1, [3, -1, -3,] 5, 3, 6, 7
1, 3, [-1, -3, 5,] 3, 6, 7
自然想到，其实可以使用一个 队列 来保存窗口数据：窗口每次滑动，我们就让后面的一个元素（-3）进队，并且让第一个元素（1）出队。进出队列的操作，只要耗费常数时间。
这种场景，可以使用 双向队列（也叫双端队列Dequeue），该数据结构可以从两端以常数时间压入/弹出元素。
在构建双向队列的时候，可以采用删除队尾更小元素的策略，所以，得到的其实就是一个 从大到小排序 的队列。
这样存储的元素，可以认为是遵循“更新更大”原则的。
public int[] maxSlidingWindow(int[] nums, int k) {
if (k == 1) return nums;
int[] result = new int[nums.length - k + 1];
ArrayDeque<Integer> deque = new ArrayDeque<>();
// 初始化双向队列
for (int i = 0; i < k; i++){
while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
deque.removeLast();
}
deque.addLast(i);
}
result[0] = nums[deque.getFirst()];
// 遍历数组
for(int i = k; i < nums.length; i++){
// 说明最大的一次数据，需要删除
if (!deque.isEmpty() && deque.getFirst() == i - k){
deque.removeFirst();
}
// 删除插入，使得栈数据最大
while (!deque.isEmpty() && nums[i] > nums[deque.getLast()]){
deque.removeLast();
}
deque.addLast(i);
result[i - k + 1] = nums[deque.getFirst()];
}
return result;
}- 时间复杂度：O(N)，每个元素被处理两次：其索引被添加到双向队列中，以及被双向队列删除。
- 空间复杂度： O(N)，输出数组使用了 O(N−k+1) 空间，双向队列使用了O(k)。
左右扫描 👍
算法的主要思想，是将输入数组分割成有 k 个元素的块，然后分别从左右两个方向进行扫描统计块内的最大值，最后进行合并。这里有一些借鉴了分治和动态规划的思想。
分块的时候，如果 n % k != 0，则最后一块的元素个数可能更少。
开头元素为 i ，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块中。
为了处理更复杂的情况 2，我们需要数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向 右->左。right 数组和 left 除了方向不同以外基本一致。
两数组合在一起，就可以提供相邻两个块内元素的全部信息。
现在我们考虑从下标 i 到下标 j的滑动窗口。 可以发现，这个窗口其实可以堪称两部分：以两块的边界（比如叫做m）为界，从i到m属于第一个块，这部分的最大值，应该从右往左，看right[i]；而从m到j属于第二个块，这部分的最大值应该从左往右，看left[j]。因此合并起来，整个滑动窗口中的最大元素为 max(right[i], left[j])。
同样，如果是第一种情形，都在一个块内，用上面的公式也是正确的（这时right[i] = left[j]，都是块内最大值）。
这个算法时间复杂度同样是O(N)，优点是不需要使用除数组之外的任何数据结构.
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
// 定义存放块内最大值的数组left、right
int[] left = new int[n];
int[] right = new int[n];
// 遍历数组，左右双扫描
for (int i = 0; i < n; i++){
if (i % k == 0){
left[i] = nums[i];
} else {
left[i] = Math.max(left[i-1], nums[i]);
}
int j = n - i - 1;
if (j % k == k - 1 || j == n-1){
right[j] = nums[j];
} else {
right[j] = Math.max(right[j+1], nums[j]);
}
}
for (int i = 0; i < n - k + 1; i++){
result[i] = Math.max(right[i], left[i + k - 1]);
}
return result;
}
- 时间复杂度：O(N)，我们对长度为 N 的数组处理了 3次（实际代码中只有两个循环，左右扫描是对称的，我们在一次遍历中同时处理了）。因为避免了出队入队的操作，所以这个算法在实际运行中，耗费时间要明显少于之前的算法。
- 空间复杂度：O(N)，用于存储长度为 N 的 left 和 right 数组，以及长度为 N - k + 1的输出数组
最小覆盖子串（#76）
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
示例 2：
输入：s = “a”, t = “a”
输出：“a”
提示：
l 1 <= s.length, t.length <= 105
l s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗
解题思路
比较子串每个字符含有的数量 < 主串的每个字符的数量。
优化思路
- 假设最终找到的位置为 startIndex和endIndex。则应该 定位 startIndex然后去移动endIndex。
- 优化思路1: 如果应该找到了匹配的子串。而endIndex不用继续往后移动了。此时应该是startIndex往后移动。(可以理解为双指针法)
- 优化思路2: 每次只移动1个字符，统计子串数量时，只需进行加+1或者减-1即可，不用每次都去计算数量。
暴力法
如果T中没有重复，那这个非常简单，只要再遍历一遍T，依次检查每个字符是否包含就可以了；但现在T中字符可能重复，如果一个字符“A”重复出现3次，那我们寻找的子串中也必须有3个“A”。
子串S符合要求的条件是：统计T中每个字符出现的次数，全部小于等于在S中出现次数。
public class MinimumWindowSubstring {
public String minWindow(String s, String t) {
String minSubString = "";
HashMap<Character, Integer> tCharFrequency = new HashMap<>();
// 统计t中的字符频次
for (int i = 0; i < t.length(); i++){
char c = t.charAt(i);
int count = tCharFrequency.getOrDefault(c, 0);
tCharFrequency.put(c, count + 1);
}
// 遍历每个字符
for (int i = 0; i < s.length(); i++){
for (int j = i + t.length(); j <= s.length(); j++){
HashMap<Character, Integer> subStrCharFrequency = new HashMap<>();
for (int k = i; k < j; k++){
char c = s.charAt(k);
int count = subStrCharFrequency.getOrDefault(c, 0);
subStrCharFrequency.put(c, count + 1);
}
if (check(tCharFrequency, subStrCharFrequency) && (j - i < minSubString.length() || minSubString.equals("") )){
minSubString = s.substring(i, j);
// 这里明显是个优化思路。即如果已经找到后续的就不用匹配了，因为是求最短，后续肯定只会更长。 这里如果加break等价于 双指针法。
// if(!minSubString.equals("")){
// break;
// }
}
}
}
return minSubString;
}
// 定义一个方法，用来检查子串是否符合要求
public boolean check( HashMap<Character, Integer> tFreq, HashMap<Character, Integer> subStrFreq ){
for (char c: tFreq.keySet()) {
if (subStrFreq.getOrDefault(c, 0) < tFreq.get(c)){
return false;
}
}
return true;
}
}
滑动窗口
public String minWindow(String s, String t) {
String minSubString = "";
HashMap<Character, Integer> tCharFrequency = new HashMap<>();
for (int i = 0; i < t.length(); i++){
char c = t.charAt(i);
int count = tCharFrequency.getOrDefault(c, 0);
tCharFrequency.put(c, count + 1);
}
HashMap<Character, Integer> subStrCharFrequency = new HashMap<>();
int lp = 0, rp = 1;
int charCount = 0;
while ( rp <= s.length() ){
char newChar = s.charAt(rp - 1);
if ( tCharFrequency.containsKey(newChar) ){
subStrCharFrequency.put(newChar, subStrCharFrequency.getOrDefault(newChar, 0) + 1);
if ( subStrCharFrequency.get(newChar) <= tCharFrequency.get(newChar) )
charCount ++;
}
while ( charCount == t.length() && lp < rp ){
if ( minSubString.equals("") || rp - lp < minSubString.length() ){
minSubString = s.substring(lp, rp);
}
char removedChar = s.charAt(lp);
if ( tCharFrequency.containsKey(removedChar) ){
subStrCharFrequency.put(removedChar, subStrCharFrequency.getOrDefault(removedChar, 0) - 1);
if ( subStrCharFrequency.get(removedChar) < tCharFrequency.get(removedChar) )
charCount --;
}
lp++;
}
rp++;
}
return minSubString;
}
找到字符串中所有字母异位词（#438）
其它优秀解析：
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
l 字母异位词指字母相同，但排列不同的字符串。
l 不考虑答案输出的顺序。
示例 1:
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
示例 2:
输入:
s: “abab” p: “ab”
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词
解题分析
优秀解析：
字母异位词（438） | 小浩算法
“字母异位词”，指“字母相同，但排列不同的字符串”。注意这里所说的“排列不同”，是所有字母异位词彼此之间而言的，并不是说要和目标字符串p不同。
另外，我们同样应该考虑，p中可能有重复字母
暴力法
最简单的想法，自然还是暴力法。就是直接遍历s中每一个字符，把它当作子串的起始，判断长度为p.length()的子串是否是p的字母异位词就可以了。
考虑到子串和p中都可能有重复字母，我们还是用一个额外的数据结构，来保存每个字母的出现频次。由于本题的字符串限定只包含小写字母，所以我们可以简单地用一个长度为26的int类型数组来表示，每个位置存放的分别是字母a~z的出现个数。
public class FindAllAnagrams {
public List<Integer> findAnagrams(String s, String p) {
int[] pCharCounts = new int[26];
for ( int i = 0; i < p.length(); i++ ){
pCharCounts[p.charAt(i) - 'a'] ++;
}
ArrayList<Integer> result = new ArrayList<>();
// 遍历s
for ( int i = 0; i <= s.length() - p.length(); i++ ){
boolean isMatch = true;
int[] subStrCharCounts = new int[26];
for ( int j = i; j < i + p.length(); j++ ){
subStrCharCounts[s.charAt(j) - 'a'] ++;
if ( subStrCharCounts[s.charAt(j) - 'a'] > pCharCounts[s.charAt(j) - 'a'] ) {
isMatch = false;
break;
}
}
if ( isMatch )
result.add(i);
}
return result;
}
}
复杂度分析
时间复杂度：O(|s| * |p|)，其中|s|表示s的长度，|p|表示p的长度。时间开销主要来自双层循环，循环的迭代次数分别是(s.length-p.length+1)和 p.length, 所以时间复杂度为O((|s|-|p|+1) * |p|), 去除低阶复杂度，最终的算法复杂度为 O(|s| * |p|)。
空间复杂度：O(1)。需要两个大小为 26 的计数数组，分别保存p和当前子串的字母个数。尽管循环迭代过程中在不断申请新的空间，但是上一次申请的数组空间应该可以得到复用，所以实际上一共花费了2个数组的空间，因为数组大小是常数，所以空间复杂度为O(1)。
双指针法
暴力法的缺点是显而易见的：时间复杂度较大，运行耗时较长。
我们在暴力求解的时候，其实对于很多字母是做了多次统计的。子串可以看作字符串上开窗截取的结果，自然想到，可以定义左右指针向右移动，实现滑动窗口的作用。在指针移动的过程中，字符只会被遍历一次，时间复杂度就可以大大降低
public List<Integer> findAnagrams(String s, String p) {
int[] pCharCounts = new int[26];
for ( int i = 0; i < p.length(); i++ ){
pCharCounts[p.charAt(i) - 'a'] ++;
}
ArrayList<Integer> result = new ArrayList<>();
// 定义左右指针
int lp = 0, rp = 1;
int[] subStrCharCounts = new int[26];
while ( rp <= s.length() ){
char newChar = s.charAt(rp - 1);
subStrCharCounts[newChar - 'a'] ++;
// 新增一个时，一直递归到下一个
while ( subStrCharCounts[newChar - 'a'] > pCharCounts[newChar - 'a'] && lp < rp ){
char removedChar = s.charAt(lp);
subStrCharCounts[removedChar - 'a'] --;
lp ++;
}
if ( rp - lp == p.length() )
result.add(lp);
rp ++;
}
return result;
}复杂度分析
时间复杂度：O(|s|)。 窗口的左右指针最多都到达 s 串结尾，s 串每个字符最多被左右指针都经过一次，所以时间复杂度为O(|s|)。
空间复杂度：O(1)。只需要两个大小为 26 的计数数组，大小均是确定的常量，所以空间复杂度为O(1)。
无重复的最长子串(#3)
和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
输入：target = 9
输出：[[2,3,4],[4,5]]
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
int left = 1;
int right = 1;
int win = 0;
// 以中数进行判断。左基准
while (left <= target / 2) {
if (win < target) {
win += right;
right++;
} else if (win > target) {
win -= left;
left++;
} else {
int[] arr = new int[right-left];
for (int k = left; k < right; k++) {
arr[k-left] = k;
}
res.add(arr);
win -= left;
left++;
}
}
return res.toArray(new int[res.size()][]);
}
}