Java实现 LeetCode 659 分割数组为连续子序列 (哈希)

659. 分割数组为连续子序列 输入一个按升序排序的整数数组（可能包含重复数字），你需要将它们分割成几个子序列，其中每个子序列至少包含三个连续整数。返回你是否能做出这样的分割？ 示例 1： 输入: [1,2,3,3,4,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3 3, 4, 5 示例 2： 输入: [1,2,3,3,4,4,5,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3, 4, 5 3, 4, 5 示例 3： 输入: [1,2,3,4,4,5] 输出: False 提示： 输入的数组长度范围为 [1, 10000] 在LeetCode的第659题“分割数组为连续子序列”中，主要涉及的问题是判断一个升序排列且可能包含重复元素的整数数组，是否可以被分割成多个至少包含三个连续整数的子序列。这是一个组合问题，可以通过哈希表来优化解题过程。以下是对解题思路的详细分析： 我们需要一个数据结构来存储数组中的每个元素及其出现的次数。由于题目要求判断连续子序列，而数组是有序的，因此哈希表（在这里使用的是HashMap）是一个理想的选择，因为它提供了O(1)的查找和插入时间复杂度。 在Java的`Solution`类中，我们创建了一个`HashMap<Integer, Integer>`类型的变量`map`，用于存储数组`nums`中的每个元素及其出现的次数。遍历数组，对于每个元素`i`，我们在哈希表`map`中查找`i`的值并加1，表示`i`的计数增加。 接下来，我们再次遍历数组`nums`，但这次的目标是检查每个元素是否能作为连续子序列的起始元素。对于每个元素`i`，我们初始化一个变量`subNum`表示当前子序列的元素个数，以及一个变量`p`表示子序列中下一个元素应出现的次数。初始时，`p`等于1，因为我们需要找到至少3个连续的元素。 进入一个循环，只要当前元素`next`在哈希表`map`中且其计数大于或等于`p`，我们就可以将`next`从子序列中移除（减去1），同时更新子序列的元素个数`subNum`，并将`next`设置为其下一个连续的元素。这个循环直到无法找到足够多的连续元素为止。 如果在结束循环后，`subNum`大于0且小于3，这意味着找到了一个连续子序列，但它的长度不满足题目要求（即少于3个元素），此时返回`false`，表示不能进行有效的分割。如果遍历完整个数组后没有遇到这种情况，则返回`true`，表示可以进行有效的分割。 通过这种方法，我们可以有效地检查整个数组是否可以被分割成满足条件的连续子序列，且在O(n)的时间复杂度内完成，其中n是数组的长度。这种方法充分利用了哈希表的特性，减少了重复检查和回溯，提高了算法的效率。 本题的关键在于使用哈希表记录元素的频率，然后通过循环遍历数组，判断每个元素能否作为连续子序列的起点，并更新哈希表，以检查是否能找到满足条件的连续子序列。这是一种典型的哈希表在解决组合问题中的应用。