题目描述

Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]
Output: False

Constraints:

• 1 <= nums.length <= 10000

题意：给一个已经排好序的数组，请问能否将数组分隔成一到多个子序列，其中每个子序列包含至少三个连续的数字。

算法1

(贪心，哈希) $O(n)$

题解：这题的要求很像打扑克牌的时候将牌凑成顺子。我们先使用一个哈希表cnt存储每个数字出现了多少次，再用一个哈希表chain_cnt存储以某个数字结尾的合法数字链的个数，这里的数字链指的是长度大于等于3的连续三个数字组成的链，如[3,4,5]。我们先遍历一遍数字，统计每个数字出现了多少次，再从前往后遍历一次，经过这一次循环后，哈希表cnt的含义变为每个数字还有多少个没被使用过。

首先判断这个数字是否已经透支使用完了，如果没有没使用完，说明当前我们需要使用这个数字来放在一个数字链当中。

遍历到数字x时，如果存在以x - 1结尾的合法数字链，那么我们直接将这个数字插入到这个数字链末尾，执行

chain_cnt[x] ++,chain_cnt[x - 1] --,cnt[x] --;

如果不存在以x - 1结尾的合法数字链，那么我们尝试用x作为一个新的数字链的开头，只有当cnt[x + 1] > 0 && cnt[x + 2] > 0的时候，才有可能让x作为一个新的合法数字链的开头，执行：

chain_cnt[x + 2] ++,cnt[x + 1] --,cnt[x + 2] --;

如果上面两个都不满足的话，那么说明遇到了非法数字，直接返回false。

    bool isPossible(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) return false;
        unordered_map<int,int> cnt;
        unordered_map<int,int> chain_cnt;
        for(int i = 0 ; i < n ; i ++)
            cnt[nums[i]] ++;
        for(int i = 0 ; i < n ; i ++)
        {
            if(cnt[nums[i]] == 0)
                continue;
            cnt[nums[i]] --;
            if(chain_cnt[nums[i] - 1] > 0)
            {
                chain_cnt[nums[i] - 1] --;
                chain_cnt[nums[i]] ++;
            }else if(cnt[nums[i] + 1] > 0 && cnt[nums[i] + 2] > 0)
            {
                cnt[nums[i] + 1] --;
                cnt[nums[i] + 2] --;
                chain_cnt[nums[i] + 2] ++;
            }else
                return false;
        }
        return true;
    }