力扣之滑动窗口《循序渐进》（209.长度最小的子数组、904. 水果成篮）

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。 用的双指针

第一题简单题熟悉一下
第二题中等题加强一下

第一题 209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续
子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)

class Solution {
    

    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
    
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;//表示int最大值，挺大的2几几把 for (int right = 0; right < nums.length; right++) {
    
            sum += nums[right];
            while (sum >= s) {
    
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

第二题 904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

 //滑动窗口（双指针）左指针判断条件 右指针负责遍历
class Solution {
    
    public int totalFruit(int[] tree) {
    
        if (tree == null || tree.length == 0) return 0;
        int n = tree.length;

        Map<Integer, Integer> map = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int i = 0; i < n; i++) {
     //有三个不相同的水果时候
            map.put(tree[i], map.getOrDefault(tree[i], 0) + 1); 
            while (map.size() > 2) {
     
                map.put(tree[left], map.get(tree[left]) - 1);
                 //此处不能直接remove，因为考虑到 [3,3,3,1,...]这种情况
                 //不然333直接删完了
                if (map.get(tree[left]) == 0) map.remove(tree[left]); 
                left++;
            }
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }
}

解释map.
map.getOrDefault(Object key, V defaultValue);

①map中存在key，value返回key对应的value即可。

②map中不存在key，value则返回defaultValue(默认值)。

map.put(num,map.getOrDefault(num, 0) + 1)

①map中含有num的话，就将num对应的value值+1

②map中不含有num的话，num对应的value对应的默认值赋值为0，然后再+1

所以这个方法适合统计数字num出现的次数