659 分割数组为连续子序列（贪心、哈希表）

快来打我* 2022-08-29 10:27 146阅读 0赞

**1. 问题描述：**

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。如果可以完成上述分割，则返回 true ；否则，返回 false 。

**示例 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 <= nums.length <= 10000来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences

**2. 思路分析：**

这道题目属于**贪心**的题目，思路比较难想。对于当前的数字x主要存在两种情况，第一种是可以接在上一个数字x - 1的后面那么就将x接在x - 1序列的后面，第二种是不可以接在x - 1后面的情况那么我们可以考虑当前的数字是否可以成为x + 1，x + 2序列的起始数字，我们可以使用两个哈希表分别存储各个出现的数字的次数与以某个数字结尾的序列是否存在，通过两个哈希表可以快速判断出当前的数字是否可以构成合法的序列，我们在循环中依次检查每一个数字的合法性即可。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        def isPossible(self, nums: List[int]) -> bool:
            # dic1用来存储nums中各个数字出现的次数, dic2用来存储以当前数字结尾的序列
            dic1, dic2 = collections.defaultdict(int), collections.defaultdict(int)
            for x in nums:
                dic1[x] += 1
            for x in nums:
                if dic1[x] == 0: continue
                # 第一种情况当前的x能够接在x - 1的后面
                if dic2[x - 1]:
                    dic2[x - 1] -= 1
                    dic2[x] += 1
                    # 当前数字使用过之后那么对应的次数减1
                    dic1[x] -= 1
                # 第二种情况当前的x - 1不存在那么考虑当前的x为开始的序列并且当前序列的长度应该要大于3
                elif dic1[x + 1] and dic1[x + 2]:
                    dic2[x + 2] += 1
                    # 当前数字使用过之后那么对应的次数减1
                    dic1[x] -= 1
                    dic1[x + 1] -= 1
                    dic1[x + 2] -= 1
                # 其余情况返回False
                else:return False
            return True