滑动窗口
# lc209. 长度最小的子数组/最短中等hot
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
2
3
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
2
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
2
思路:滑动窗口 前缀和
var minSubArrayLen = function(target, nums) {
const len = nums.length
const sum = new Array(len + 1).fill(0)
let l = 0, r = 0, min = +Infinity
while(r <= len) {
if(sum[r] - sum[l] < target) {
sum[++r] = sum[r - 1] + nums[r - 1]
} else {
min = Math.min(min, r - l)
l++
}
}
// 最后一步判断 是否所有数加起来是否小于target 或者判断min是否还等于+Infinity也可以
return sum[r - 1] < target ? 0: min
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
时间复杂度:O(n)
空间复杂度:O(n)
降低空间复杂度
var minSubArrayLen = function (target, nums) {
const len = nums.length;
// const sum = new Array(len + 1).fill(0)
let l = 0,
r = 0,
min = +Infinity,
sum = 0;
while (r < len) {
sum += nums[r];
while (sum >= target) {
min = Math.min(min, r - l + 1);
sum -= nums[l];
l++;
}
r++;
}
return min === +Infinity ? 0 : min;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
时间复杂度:O(n)
空间复杂度:O(1)
# lc239. 滑动窗口最大值困难
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
2
3
4
5
6
7
8
9
10
11
12
13
示例 2：
输入：nums = [1], k = 1
输出：[1]
2
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
2
示例 4：
输入：nums = [9,11], k = 2
输出：[11]
2
示例 5：
输入：nums = [4,-2], k = 2
输出：[4]
2
法一： 暴力法
思路：
声明数组
arr存放滑动窗口res存放最大值进入遍历
如果当前索引小于
k - 1的话 则不满足滑动窗口大小，继续往arr插进元素如果当前索引大于等于
k - 1那就比较里面的k个元素中最大的 然后push进res中
因为暴力法 会有n - k + 1个窗口生成
因此时间复杂度为 O((n - k + 1)k) = O(nk) 会超出时间限制
var maxSlidingWindow = function(nums, k) {
if(k === 1) return nums
const res = []
const arr = []
for(let i = 0; i < nums.length; i++) {
arr.push(nums[i])
if(i >= k - 1) {
res.push(Math.max(...arr))
arr.shift()
}
}
return res
};
2
3
4
5
6
7
8
9
10
11
12
13
14
因为超出时间限制，不通过
法二 双向队列(单调队列)
思路：
总结就是保证最大的数字在队头
假如滑动窗口移动，那么就逐步把其他元素出队
const maxSlidingWindow = function (nums, k) {
const deque = []
const result = []
for (let i = 0; i < nums.length; i++) {
// 把滑动窗口之外的踢出
if (i - deque[0] >= k) {
deque.shift()
}
while (nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop()
}
deque.push(i)
if (i >= k - 1) {
result.push(nums[deque[0]])
}
}
return result
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# lc03. 无重复字符的最长子串中等hot
题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
2
3
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
2
3
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
2
3
4
示例 4:
输入: s = ""
输出: 0
2
法一：滑动窗口
维护一个队列
字符的每个字符准备入队
判断队列里是否已经存在相同字符
- 如果没有则入队
- 如果有的话 保存队列中相同字符的索引
index，并把0 ~ index + 1出队- 然后在把这个字符入队
判断此时队列的长度和原来的最大值哪个大
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let arr = [], index, max = 0
for(let i = 0; i < s.length; i++) {
index = arr.indexOf(s[i])
if(index !== -1) {
arr.splice(0, index + 1)
}
arr.push(s.charAt(i))
max = Math.max(max, arr.length)
}
return max
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度O(n ^ 2) 因为for为O(n) 里面的 arr.indexOf() 时间复杂度为 O(n) , arr.splice(0, index+1) 的时间复杂度也为 O(n)
空间复杂度O(n)
法二：
js api的map
思路：
维护一个
map变量
i为无重复的起始位，j为当前元素的索引值进入一次字符串
s的循环判断元素
s[i]是否在map里面- 如果有的话，则更新无重复子串开始下标
i为相同字符的下一位置 - 解释一下上面 假如输入的字符串是
abcabcbb那么当s[i]为第四个字符a的时候map里面存在对应的索引为0，那么这个时候要比较索引0 + 1和原来i中谁大
- 如果有的话，则更新无重复子串开始下标
更新
max
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let max = 0
let map = new Map()
for(let i = 0, j = 0; j < s.length; j++) {
// 为什么下面还需要和原来的i比较呢
// 是因为假如输入的是abba
// 进行到第三位字符b的时候 i = 2; j = 2; max = 1
// 进行到第四位字符a的时候 假如还是等于map.get(s[j])的话，会导致 i = 1 j = 3 max = 3
// 其最大无重复字符串为bba？
// 很显然不对，但Math.max(map.get(s[j]) + 1, i)保证了i不会出错
if(map.has(s[j])) i = Math.max(map.get(s[j]) + 1, i)
max = Math.max(j - i + 1, max)
map.set(s[j], j)
}
return max
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
时间复杂度:O(n)
空间复杂度:O(n)
# lc76. 最小覆盖子串困难hot
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
2
示例 2：
输入：s = "a", t = "a"
输出："a"
2
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
2
3
4
思路
要从
S字符串中找出包含T所有字母的最小子串，那么首先就得记录T中有哪些字符，然后再去遍历S，从S中寻找包含T所有字母的子串这里我们可以先用一个
map，needs来记录T中的字符，以及字符的数量然后维护一个窗口，用索引
l和r来表示这个窗口的左右边界，刚开始窗口的大小为0，即l = 0、r = 0然后开始遍历
S，从窗口的右侧依次放入元素，也用一个map，windows来记录S中的字符及其字符的数量如果
windows[c1] === needs[c1]，则说明窗口中有一个字符的数量与T中相等，则将计数器count++如果
count等于needs中的key的数量和，则说明窗口中有T中所有的字符串，此时窗口所包含的子串就是一个包含T所有字母的子串由于答案是要寻找最小的字串，所以可以记录下符合要求的子串的起始位置以及其长度，起始位置就是
l，长度为r - l找到符合要求的子串后，就开始从窗口的左侧移除字符，直到该子串不符合要求，根据将要移除的字符
c，判断windows[c] === needs[c]，如果相等则要将则将计数器count--，然后移除该字符windows[c]--，最后将左边界索引l++重复上面的逻辑找出所有可能的子串，比较每一个子串的长度，最后返回最小的子串
var minWindow = function(s, t) {
const needs = {}, window = {}
let l = 0, r = 0, minlen = +Infinity, count = 0, start = -1;
[...t].forEach(item => needs[item] ? needs[item]++ : needs[item] = 1)
const needlen = Object.keys(needs).length
while(r < s.length) {
let cur = s[r++]
window[cur] ? window[cur]++ : window[cur] = 1
// 解决了t中有重复字符 只有重复字符到达了needs的数量才增加
if(window[cur] === needs[cur]) count++
while(count === needlen) {
if(r - l < minlen) {
start = l
minlen = r - l
}
let tempCur = s[l++]
// 注意是比较了之后才-- 说明当前的字符和needs所需的字符相等，l向右移动了之后就不满足t要的字符数量，count--
if(window[tempCur]-- === needs[tempCur]) count--
}
}
// 处理s='a' t='aa'情况
return start === -1 ? '': s.substr(start, minlen)
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
时间复杂度:O(s + t)
空间复杂度:O(s + t)