LeetCode904.水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

1.常规解法（会超时）

由于题目中要求对水果的种类进行判断，于是可以用一个链表来存储水果的种类；

先对这个数组进行双重遍历，内层循环从外层循环的下一个数开始遍历，在进入外层循环之前，先将计数器加一，再将外层循环的起始水果类型放入链表中，在内层循环中，先判断这个水果类型在链表中是否存在，若存在，将计数器加一；若不存在，在判断链表中有几种水果类型，若已经有两种水果类型，直接退出内层循环，若还没到两种类型，就将这种水果的类型添加到链表中，并将计数器加一，流程图与代码如下：

    public int totalFruit(int[] fruits) {int n = fruits.length;int max = 0;//最多能放的水果的个数List<Integer> list = new LinkedList<>();//放水果类型for (int i = 0; i < n; i++) {int count = 1;//计数器list.add(fruits[i]);for (int j = i + 1; j < n; j++) {if (list.contains(fruits[j])) {count++;} else {if (list.size() == 2) {break;} else {count++;list.add(fruits[j]);}}}max = Math.max(count, max);list.clear();//清空链表中的水果种类}return max;}

 2.滑动窗口

在常规解法中，第一次结果与第二次结果存在重合的部分，如下图：

我们可以在第一次判断完成之后，只将3类型的水果移出篮子即可。

先定义两个指针left和right，这两个指针均指向第一个元素；定义一个数组用来存放每种类型的水果的个数（相当于水果篮）；再定义一个变量kind用来统计篮子里有多少种水果；

我们先让right指针向右移动，若right指向的水果类型再数组中有没有，即若数组中对应类型的值为0，就将kind++，并将arr[kind]++；若数组中对应类型值非0，就直接将arr[kind]++;

当篮子中水果类型超过2时（数组中非0的类型超过3），就要将left向右移动以去除一种水果，将数组中left指向的元素的数据减一，若该数据减到0时，就相当于篮子中没有这种类型的水果，统计篮子中水果的个数，再次进行循环，流程图与代码如下：

    public int totalFruit(int[] fruits) {int n = fruits.length;int[] arr = new int[n];//每种类型是否有水果int max = 0;int kind = 0;//记录类型个数for (int left = 0, right = 0; right < n; right++) {int typeRight = fruits[right];if (arr[typeRight] == 0) {kind++;}arr[typeRight]++;while (kind > 2) {arr[fruits[left]]--;if (arr[fruits[left]] == 0) {kind--;}left++;}max = Math.max(max, right - left + 1);}return max;}

 希望大家积极指导！