

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

• LeetCode: 659. 分割数组为连续子序列
  • 1、题目描述
  • 2、解题思路

1、题目描述

输入一个按升序排序的整数数组（可能包含重复数字），你需要将它们分割成几个子序列，其中每个子序列至少包含三个连续整数。返回你是否能做出这样的分割？

示例 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]

2、解题思路

• 判断标准：如果连续序列的过程中，每个元素都能够用上，并且子序列长度至少为3，就表示满足要求，如果有不能用到的子元素，就表示不满足要求

• 判断当前元素是否能够被用到：

• 如果以前面元素为结尾的子序列存在，就将子序列结尾移到当前位置上面
• 如果不存在，就判断能够以当前元素作为子序列的开始，也就是判断后面两个连续的值是否存在

from collections import Counter, defaultdict


class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False

        num_count = Counter(nums)
        end_count = defaultdict(int)

        for num in nums:
            if num_count[num] == 0:
                continue

            num_count[num] -= 1
            if end_count[num - 1] > 0:
                end_count[num - 1] -= 1
                end_count[num] += 1
            elif num_count[num + 1] > 0 and num_count[num + 2] > 0:
                num_count[num + 1] -= 1
                num_count[num + 2] -= 1
                end_count[num + 2] += 1
            else:
                return False
        return True