leetcode904-水果成篮
时间复杂度：O(n)
空间复杂度：O(1)
之前发布了一个滑动窗口的题目解答思路，参考博文：长度最小的子数组
本题也是基于滑动窗口的一个扩展题，主要解决方法是利用滑动窗口+哈希表
var totalFruit = function (fruits) {
const map = new Map();
let slow = 0; // 起始位置
let result = 0; // 最大水果数
fruits.forEach((item,index) => {
const hasFruit = map.has(item);
if (hasFruit) {
// 已经存在
map.set(item, map.get(item) + 1) // 给当前数量+1
} else {
// 篮子中还没有这个水果,初始化
map.set(item, 1)
while (map.size > 2) {
// 篮子中水果数量超出,从起始位置开始拿出水果
const delFru = fruits[slow]
map.set(delFru, map.get(delFru) - 1) //
if (map.get(delFru) === 0) {
// 篮子中已经没有此水果，如果不delete的话map.size不会更新
map.delete(delFru)
}
slow++; // 左窗口右移
}
}
result = Math.max(result,index - slow + 1)
})
return result;
};
原文地址：https://blog.csdn.net/weixin_45799371/article/details/145191974
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！