The sliding window of Li Kou "step by step" (209. The smallest sub array, 904. Fruit baskets)

So called sliding window , It's constantly adjusting the starting and ending positions of subsequences , So we can get the result that we want to think about . Double pointer for

The first question is simple
Strengthen the second medium question

The first question is 209. Subarray with the smallest length

Given a containing n An array of positive integers and a positive integer s , Find the sum of the array ≥ s The smallest length of continuity
Subarray , And return its length . If there is no sub array that meets the conditions , return 0.

Example ：

Input ：s = 7, nums = [2,3,1,2,4,3] Output ：2 explain ： Subarray [4,3] Is the smallest subarray in this condition .

In this topic, we realize the sliding window , The main points are as follows ：

• What's in the window ？
• How to move the start of a window ？
• How to move the end of a window ？

The window is Satisfy it and ≥ s The smallest length of continuity Subarray .

How the start of the window moves ： If the value of the current window is greater than s 了 , The window is about to move forward （ It's time to shrink ）.

How the end of the window moves ： The end of the window is the pointer that traverses the array , Set the starting position of the window as the starting position of the array .
It can be found that the subtlety of sliding window is based on the current subsequence and size , Constantly adjust the starting position of subsequences . So that O(n^2) The violent solution is reduced to O(n)

class Solution {
    

    //  The sliding window 
    public int minSubArrayLen(int s, int[] nums) {
    
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;// Express int Maximum , It's quite big 2 How many  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;
    }
}

The second question is 904. Fruit baskets

You are visiting a farm , The farm planted a row of fruit trees from left to right . These trees use an array of integers fruits Express , among fruits[i] It's No i The fruit on the tree species .
You want to collect as much fruit as possible . However , The owner of the farm set some strict rules , You must pick the fruit as required ：
You only have Two Basket , And each basket can only hold Single type The fruit of . There is no limit to the amount of fruit each basket can hold .
You can choose any tree to start picking , You have to go from Each tree Trees （ Including the trees that start picking ） On Just pick a fruit . The fruit picked should match the type of fruit in the basket . Every time you pick , You will move right to the next tree , And continue to pick .
Once you get to a tree , But the fruit doesn't match the type of fruit in the basket , Then you must stop picking .
Give you an array of integers fruits , Return the fruit you can collect Maximum number .

 // The sliding window （ Double pointer ） The left pointer determines the condition   The right pointer is responsible for traversing 
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++) {
     // There are three different fruit times 
            map.put(tree[i], map.getOrDefault(tree[i], 0) + 1); 
            while (map.size() > 2) {
     
                map.put(tree[left], map.get(tree[left]) - 1);
                 // You can't directly remove, Because considering  [3,3,3,1,...] This situation 
                 // Otherwise 333 Delete it directly 
                if (map.get(tree[left]) == 0) map.remove(tree[left]); 
                left++;
            }
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }
}

explain map.
map.getOrDefault(Object key, V defaultValue);

①map in key,value return key Corresponding value that will do .

②map Does not exist in the key,value Then return to defaultValue( The default value is ).

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

①map contains num Words , will num Corresponding value value +1

②map It does not contain num Words ,num Corresponding value The corresponding default value is assigned as 0, And then again +1

So this method is suitable for statistics num Number of occurrences