滑动窗口
视频精讲：滑动窗口
题单
例题
- 长度最小子串
- 打日志很重要
- 滑窗模版：先移动右边，有点像同向双指针，一般ans在左指针移动前更新
js
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (target, nums) {
//明显不能从两端相向，应该是同向
//if -> while打日志发现的；
//滑窗模版
let l = 0, r = 0, ans = Infinity, n = nums.length,sum = 0;
if (n < 2) {
if (nums[0] >= target) return 1;
}
while (r < n) {
sum += nums[r];
while(sum >= target) {
console.log('l=',l,'r=',r,sum)
ans = Math.min(ans,r - l +1)
sum -= nums[l];
l++;
}
r++;
}
return ans === Infinity ? 0 : ans;
};- 无重复的最长子串
- 哈希Map,set,get
- ??操作符
js
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
//涉及到数组or哈希map，js的哈希map没学过的:new Map(),set,get
//滑动窗口（同向双指针）：答案更新一般靠近中后
//知识点 x？？y，问号左边为null或undefined就用y；
//如果没有就右边指针往右移动，如果有就左指针往右，要记录最长的长度而且无重复map[r];while 操作左指针可以去重
let ans = 0, l = 0;
const n = s.length;
let mp = new Map();
for (let r = 0; r < n; r++) {
let c = s[r];
// mp.set('c', 1);
mp.set(c, (mp.get(c) ?? 0) + 1)
while (mp.get(c) > 1) {
mp.set(s[l], (mp.get(s[l]) ?? 0) - 1)
l++;
}
// console.log(l, mp.get(s[l]), r, mp.get(s[r]))
ans = Math.max(ans, r - l + 1)
}
return ans;
};- 乘积小于k的子数组
- 体会滑动窗口使用场景：窗口越大越不合法，越小越合法
- 体会滑动窗口的大致思路: 右指针扩大，左指针缩小，数学规律避免二次循环 r - l +1;
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numSubarrayProductLessThanK = function (nums, k) {
//由于连续，所以不能排序，大概率也不是相向双指针，看样例
//判断答案就一个sum+if，关键是怎么遍历所有情况，先考虑滑动窗口，由于子数组越长，乘积越大，越不能满足题目要求；反之，子数组越短，乘积越小，越能满足题目要求。有这种性质的题目，可以用滑动窗口解决。
//为什么滑动窗口可以遍历所有连续子数组？
//固定右边，移动左边就可以用r-l+1来避免双重循环了
let ans = 0, n = nums.length, ji = 1, l = 0;
for (let r = 0; r < n; r++) {
ji *= nums[r];
while (ji >= k) {
//写缩小逻辑
ji /= nums[l];
l++;
}
if (ji < k && l <= r) ans += r - l + 1;
}
return ans;
};作业
- 每个字符最多出现两次的最长字符串
- 注意一下map的语法
js
/**
* @param {string} s
* @return {number}
*/
var maximumLengthSubstring = function(s) {
//要求最长，越大越合法，所以同向双指针，也就是滑动窗口
//纯小写的话，直接插入map就行了
//思路：右指针从左开始扩大窗口，while循环缩小不合法的窗口，更新答案
let l = 0, n = s.length, ans = 0;
let mp = new Map();
for(let r = 0; r < n; r++){
mp.set(s[r],(mp.get(s[r])??0)+1);
while(mp.get(s[r])>2){
mp.set(s[l],mp.get(s[l])-1);
l++;
// console.log(mp.get(s[r]),l,r)
}
ans = Math.max(ans,r - l +1)
}
return ans;
};- 最多k个重复元素的最长子数组
同上题，改两个变量名就行了
- 找到最长的班重复子字符串
- 注意缩小窗口的条件和时机
js
/**
* @param {string} s
* @return {number}
*/
var longestSemiRepetitiveSubstring = function (s) {
//要求最长，越大越合法，所以同向双指针，也就是滑动窗口
//为什么要r从1开始？：经验？
let l = 0, n = s.length, cnt = 0, ans = 0;
if (n === 1) return 1;
for (let r = 1; r < n; r++) {
if (s[r] === s[r - 1]) cnt++;
if (n === 2 && cnt === 1) cnt = 0;
while (cnt > 1) {
if (s[l] === s[l + 1]) cnt--;
l++;
// console.log(mp.get(s[r]),l,r)
}
if (cnt <= 1) ans = Math.max(ans, r - l + 1);
}
return ans;
};- 数组最大美丽值
- 选区间问题：是否排序，越大越合法，缩小窗口的时机
- console.log对算法时间也有贡献
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumBeauty = function (nums, k) {
//由于可以操作任意次，那可以排序
nums.sort((a, b) => a - b);
//越大越合法，滑动窗口
//数学推导，带范围的可以在图上画好区间，发现要求的就是最多交集个数，也就是左边+k大于等于右边-k，那就用到反面条件来缩小窗口
let ans = 0, l = 0, n = nums.length;
for (let r = 0; r < n; r++) {
// console.log('r - l', nums[r] - nums[l])
while (nums[r] - nums[l] > 2 * k) {
l++;
}
//合法的时候记录最大的
ans = Math.max(ans, r - l + 1);
// console.log(l, r, ans)
}
return ans;
};- 最大连续1的个数三
- 最有成就感的一题，做的很爽，思路一下就上来了，所以还是要多总结题目的特征，多总结调试经验
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var longestOnes = function (nums, k) {
//越大越合法，所以考虑相向双指针
//要统计频次，哈希数组
//缩小窗口的条件：0的次数大于k
//在哪里打印？哪里变了？l,r,mp
let l = 0, ans = 0, n = nums.length;
let mp = new Map();
for (let r = 0; r < n; r++) {
mp.set(nums[r], (mp.get(nums[r]) ?? 0) + 1)
while (mp.get(0) > k) {
mp.set(nums[l], (mp.get(nums[r]) ?? 0) - 1);
l++;
// console.log('进循环了')
}
ans = Math.max(ans, r - l + 1);
}
return ans;
};附录
JS中的哈希Map
- new,set,get,has,delete, 在 JavaScript 中，主要有两种方式实现哈希 map 的功能：
1. Map 对象（推荐使用）
基本操作
javascript
// 创建 Map
const map = new Map();
// 添加元素
map.set('name', '张三');
map.set('age', 25);
map.set({ id: 1 }, '对象作为键'); // 键可以是任何类型
// 获取元素
console.log(map.get('name')); // '张三'
console.log(map.get('age')); // 25
// 检查键是否存在
console.log(map.has('name')); // true
console.log(map.has('gender')); // false
// 删除元素
map.delete('age');
// 获取大小
console.log(map.size); // 2
// 清空 Map
map.clear();遍历 Map
javascript
const map = new Map([
['name', '张三'],
['age', 25],
['city', '北京']
]);
// 遍历键值对
for (const [key, value] of map) {
console.log(`${key}: ${value}`);
}
// 遍历键
for (const key of map.keys()) {
console.log(key);
}
// 遍历值
for (const value of map.values()) {
console.log(value);
}
// 使用 forEach
map.forEach((value, key) => {
console.log(`${key}: ${value}`);
});从数组创建 Map
javascript
// 二维数组转 Map
const entries = [
['name', '李四'],
['age', 30],
['city', '上海']
];
const map = new Map(entries);
// 对象转 Map
const obj = { name: '王五', age: 28 };
const mapFromObj = new Map(Object.entries(obj));2. 普通对象（简单场景）
基本操作
javascript
// 创建对象作为 map
const map = {};
// 添加属性
map['name'] = '赵六';
map.age = 35;
// 访问属性
console.log(map['name']); // '赵六'
console.log(map.age); // 35
// 检查属性是否存在
console.log('name' in map); // true
console.log(map.hasOwnProperty('name')); // true
// 删除属性
delete map.age;
// 获取所有键
console.log(Object.keys(map)); // ['name']
console.log(Object.values(map)); // ['赵六']注意事项
javascript
// 对象的键会被转换为字符串
const map = {};
map[true] = '布尔值';
map[123] = '数字';
map[{ a: 1 }] = '对象';
console.log(map); // { '123': '数字', true: '布尔值', '[object Object]': '对象' }3. Map vs 对象的比较
| 特性 | Map | 对象 |
|---|---|---|
| 键的类型 | 任何类型（函数、对象、基本类型） | 字符串或 Symbol |
| 键的顺序 | 插入顺序 | 普通属性无序，整数键按升序 |
| 大小属性 | size 属性 | 需要手动计算 |
| 性能 | 频繁增删查改性能更好 | 适合小规模静态数据 |
| 迭代 | 直接可迭代 | 需要 Object.keys() 等 |
4. 实用示例
计数器
javascript
// 使用 Map 统计字符出现次数
function countCharacters(str) {
const count = new Map();
for (const char of str) {
count.set(char, (count.get(char) || 0) + 1);
}
return count;
}
const result = countCharacters('hello');
console.log(result.get('l')); // 2缓存数据
javascript
class Cache {
constructor() {
this.cache = new Map();
}
set(key, value, ttl = 5000) {
this.cache.set(key, {
value,
timestamp: Date.now(),
ttl
});
}
get(key) {
const item = this.cache.get(key);
if (!item) return null;
if (Date.now() - item.timestamp > item.ttl) {
this.cache.delete(key);
return null;
}
return item.value;
}
}
// 使用示例
const cache = new Cache();
cache.set('user1', { name: '张三' }, 3000);
console.log(cache.get('user1')); // { name: '张三' }5. 最佳实践建议
- 优先使用 Map：除非需要与 JSON 互转或有特殊需求
- 需要与 JSON 交互：使用普通对象
- 需要复杂键：必须使用 Map
- 频繁增删：Map 性能更好
- 需要保持顺序：Map 保持插入顺序
选择哪种方式取决于你的具体需求！
空值合并运算符
cnt.set(c, (cnt.get(c) ?? 0) + 1); 这个语法叫做空值合并运算符（Nullish Coalescing Operator）。
正式名称
- 中文：空值合并运算符
- 英文：Nullish Coalescing Operator
语法特点
- 符号：
?? - 引入时间：ES2020（ECMAScript 2020）
- 作用：专门用于处理
null和undefined的情况
相关的现代 JavaScript 语法
1. 可选链操作符（Optional Chaining）?.
经常和 ?? 一起使用：
javascript
const obj = {};
// 如果 obj.user 不存在，返回 undefined 而不是报错
const name = obj.user?.name ?? '匿名';
console.log(name); // '匿名'2. 逻辑或赋值（Logical OR assignment）||=
javascript
// 传统写法
if (!x) {
x = 10;
}
// 现代写法
x ||= 10; // x 如果是假值，就赋值为 103. 空值合并赋值（Nullish coalescing assignment）??=
javascript
// 只有 x 是 null 或 undefined 时才赋值
x ??= 10;
let a = 0;
a ??= 100; // a 还是 0（因为 0 不是 null/undefined）
let b = null;
b ??= 100; // b 变为 100这些运算符的兼容性
- 所有现代浏览器都支持
- Node.js 14+ 支持
- TypeScript 3.7+ 支持
- 如果需要兼容旧环境，可以使用 Babel 转译
简单来说，?? 就是 JavaScript 中专门用来处理"值不存在"情况的运算符！