Leetcode题目最怕的是，没有用对方法，编码5分钟，调试2小时，肯定就GG了。掌握常用套路还是很重要的。
滑动窗口一般用于处理数组里最长或最短子序列的问题。滑动窗口的过程中记录一些有用的数据，比起暴力拆解法，极大的提升算法效率。
很典型的滑动窗口的题，用到了双端队列来模拟，保证队列里的元素是单调减的，也就是队首是最大元素，有点像前面练习过的单调栈。遍历到一个新元素事，如果队列里有比当前元素小的，就将其移除队列，保证队列递减。当队列元素位置与新加入元素的位置只差大于k，就将队首元素移除。
上代码伺候：
public int[] maxSlidingWindow(int[] nums, int k) {
// 暂存结果
int[] result = new int[nums.length - k + 1];
// 双端队列作为窗口，开始滑动,存下标
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 保值 deque左遍的数比新入队的大,
while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
deque.removeLast();
}
// 从尾部加入
deque.addLast(i);
// 从头部移除
if (deque.getFirst() == i - k) {
deque.removeFirst();
}
// 输出结果,当i没有k-1打的时候，不输入结果
if (i >= k - 1) {
result[i - k + 1] = nums[deque.getFirst()];
}
}
return result;
}
这个题看似不难，可以暴力拆解，容易超时，最开始做的时候的答案
class Solution {
int lengthOfLongestSubstring(String s) {
int start = 0;
int end = 0;
int maxlength = 0;
String tempstr = "";
for(int i=0;i< s.length();i++) {
for(int j=i+1;j<= s.length();j++) {
tempstr = s.substring(i,j);
if(tempstr.length() == tempstr.chars().distinct().count()) {
maxlength = Math.max(tempstr.length(),maxlength);
}
}
}
return maxlength;
}
}
绝妙的操作，但是有一个性能用例过不了，时间复杂过高。这个时候滑动窗口很适合了，
public int lengthOfLongestSubstring(String s) {
int result = 0;
int[] freg = new int[256];
// 窗口的左右边界
int left = 0;
int right = -1;
char[] charArray = s.toCharArray();
while (left < charArray.length) {
// 满足添加，向右移动
if (right + 1 < charArray.length && freg[charArray[right + 1]] == 0) {
right++;
freg[charArray[right]]++;
} else {
freg[charArray[left]]--;
left++;
}
result = Math.max(result, right - left + 1);
}
return result;
}
用freg数组的目的是方便判断字符是否已经在窗口中，一般设置left初始值是0，right初始值为-1，简单总结出滑动窗口题的模板：
int left = 0;// 左边界
int right =-1;// 右边界
int result = 0;// 结果值
// 存储暂存结果的一些结构
whlie(left <边界) {
if(right+1< 边界 && 题目约束调理) {
right++;
暂存结构变化；
} else{
暂存结构变化;
left++;
}
if(满足条件) {
result = Math.max(result, right - left + 1);// 改变result的值
}
}
return result;
其实就是提供一个思路，快速实现代码，重点还是调试🤠，考试的时候就不要死磕了，觉得陷入坑了，要及时换思路，可能还有救🤑
区间可长可短，可滑动，求最小，上代码
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int right = -1;
int result = Integer.MAX_VALUE;
int sum = 0;
while (left < nums.length) {
if (right + 1 < nums.length && sum < s) {
//right右滑
right++;
sum += nums[right];
} else {
//left 右滑
left++;
sum -= nums[left];
}
// 判断是否满足条件
if (sum >= s) {
result = Math.min(result, right - left + 1);
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
