LeetCode 659. 分割数组为连续子序列

题目描述

给你一个按升序排序的整数数组num（可能包含重复数字），请你将它们分割成一个或多个长度为3的子序列，其中每个子序列都由连续整数组成。

如果可以完成上述分割，则返回true；否则，返回false。

示例一

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5

示例二

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5

示例三

输入: [1,2,3,4,4,5]
输出: False

题解

首先按照贪心的思路考虑该问题：

• 新的数应该尽可能把连续 2 个的数凑到满 3 个（如果凑不够，就要直接返回false）
• 当所有的 2 个数都凑到满 3 个后，尽可能把 1 个的数凑到满 2 个（如果凑不够，直接返回false)
• 当所有的 1 个都凑到 2 个后，把剩下的数尽可能和之前已经凑成一组（这样不会引入新的连续 1 个数，同时后面的连续的数也可以继续向后续）
• 只有还有多余的数必须单独成组，成为新的连续 1 个的

综上所述，只需要按照要求维护“连续 1 个”，“连续 2 个”，“连续 3 个以上”的个数即可

LeetCode 题解里有人给出了时间复杂度 $O(n)$，空间复杂度 $O(1)$ 的解法，相当于下面代码修改为一边计算个数，一边进行判断的情况。

代码

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        if len(nums) == 0:
            return True
        count = {}
        for n in nums:
            count[n] = count.get(n, 0) + 1

        pre = -1
        l = [0, 0, 0, 0]
        for i in range(min(nums), max(nums) + 1):
            if pre == -1:
                # 没有前一个数
                if count.get(i, 0) > 0:
                    # 当前数有值，则更新为当前数
                    l[1] = count[i]
                    l[2] = 0
                    l[3] = 0
                    pre = i
                else:
                    continue
            else:
                if count.get(i, 0) == 0:
                    # 存在前一个数，同时当前数不存在
                    if l[1] != 0 or l[2] != 0:
                        # 还有没凑够 3 个的数
                        return False
                    else:
                        # 全部都凑够 3 个，从新开始
                        l[3] = 0
                        pre = -1
                        continue
                else:
                    c = count[i]
                    temp = l[3]
                    # 优先凑 3 个
                    if c >= l[2]:
                        # 足够把 2 个的都凑成 3 个
                        c -= l[2]
                        l[3] = l[2]
                        if c >= l[1]:
                            # 足够把所有 1 个的凑成 2 个
                            c -= l[1]
                            l[2] = l[1]
                            if c > temp:
                                # 剩下的都补给原本就有 3 个的仍有剩余
                                l[1] = c - temp
                                l[3] += temp
                            else:
                                # 剩下的都补给原本就有 3 个的
                                l[1] = 0
                                l[3] += c
                        else:
                            # 只能把部分 1 个凑成 2 个
                            return False
                    else:
                        # 只能把部分 2 个凑成 3 个
                        return False
        return l[1] == 0 and l[2] == 0