力扣904. 水果成篮

力扣题目链接

1.题目介绍

题目翻译成人话就是 ：找包含两种元素的最长子串，返回其长度。

2.解法

实现滑动窗口，主要确定如下三点：
1.窗口内是什么？ 窗口是只含两种元素的子串。
2.如何移动窗口的起始位置？当窗口中出现超过两种元素（即哈希表中出现超过两个键值对），就需要不断移动 left，并将 fruits[left] 从哈希表中移除，直到哈希表满足要求为止。
3.如何移动窗口的终止位置？窗口的结束位置就是遍历整个数组的指针，也就是for循环里的索引。

class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int left = 0, res = 0;
        for (int right = 0; right < n; right++) {
            //存储这个窗口内的数以及出现的次数
            hashMap.put(fruits[right], hashMap.getOrDefault(fruits[right], 0) + 1);
            //动态调节滑动窗口的起始位置
            while (hashMap.size() > 2) {
                hashMap.put(fruits[left], hashMap.get(fruits[left]) - 1);
                //出现次数减小为0时需要将对应的键值对从哈希表中移除
                if (hashMap.get(fruits[left]) == 0) {
                    hashMap.remove(fruits[left]);
                }
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22