首页分享题解：农场采摘水果问题

题解：农场采摘水果问题

来源：花匠小妙招时间：2025-09-27 10:29

题目解析

附上题目链接 344 农场采摘水果问题

这道题的核心是通过滑动窗口的技巧，在整数数组中找到满足题目条件的最长子数组长度。题目本质是一个经典的双指针问题，利用滑动窗口机制对数组进行动态调整，以满足每次操作的时间复杂度尽可能低。

我们将每个水果类型视作一个集合元素，数组代表这些元素的排列。小U的限制是只能携带两个篮子，因此滑动窗口需要控制在两种类型的水果内。这意味着我们需要一个动态数据结构来记录窗口内的水果种类及其数量，方便窗口的扩展和收缩。

解题思路

1. 数据结构选择

我们选择使用**哈希表（HashMap）**来存储滑动窗口内的水果种类和数量，其中：

• 键：表示水果种类；

• 值：表示该种类水果在当前窗口中的数量。

哈希表的选择是基于其对键值对的插入、删除和访问操作具有 O(1) 时间复杂度的优势。

2. 滑动窗口策略

滑动窗口本质上是通过两个指针（左指针 i 和右指针 j）界定数组的子区间：

• 右指针 j：不断向右扩展窗口，尝试将当前树上的水果加入篮子；

• 左指针 i：当窗口内水果种类超过两个时，开始收缩窗口，直至重新满足题目条件。

3. 动态维护窗口

窗口的维护分为两种情况：

• 窗口种类不超过两种：窗口可以正常扩展，并更新最大长度；

• 窗口种类超过两种：通过收缩左边界，移除水果直到种类数不超过两种。

4. 最终目标

每次右指针扩展时，记录窗口的长度并与当前最大值比较更新，最终返回最大值。

代码实现

import java.util.HashMap; public class Main { public static int solution(int[] fruits) { // write code here int n = fruits.length; HashMap<Integer, Integer> mymap = new HashMap<>(); int i = 0; int j = 0; int max_length = 0; for (j = 0; j < n; j++) { // 尝试将右窗口处的水果加入 if (mymap.containsKey(fruits[j])) { int cnt = mymap.get(fruits[j]); mymap.put(fruits[j], cnt + 1); } else { mymap.put(fruits[j], 1); } if (mymap.size() <= 2) // 如果没超，就更新最大长度 { max_length = Math.max(j - i + 1, max_length); } else// 否则收缩左窗口 { while (mymap.size() > 2) { if (mymap.get(fruits[i]) > 1) { int cnt = mymap.get(fruits[i]); mymap.put(fruits[i], cnt - 1); } else { mymap.remove(fruits[i]); } i++; } } } return max_length; } public static void main(String[] args) { System.out.println(solution(new int[] { 1, 2, 1, 2 }) == 4); System.out.println(solution(new int[] { 2, 0, 1, 2, 2 }) == 3); System.out.println(solution(new int[] { 1, 2, 3, 2, 2, 4 }) == 4); } }