659. Split Array into Consecutive Subsequences

problem desctiption

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

algorithm description

第一次想这题，没看清是连续的数字。导致分析了很久也没结果。知道是连续的数字之后，就很好办了。可以直接用hashmap保存数字出现的次数，以及保存3个以上链表的末尾节点，每次访问到数字，首先查看链表后面末尾节点是否有值，有的话直接加一。如果没有，就将这个数字后面两个数字和这个组合起来，然后加入到将这个链表末尾节点加入hashmap，如果不能进行上面两个操作，说明这里有问题

code

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int,int> cut,tail;
        for(auto num:nums)
            cut[num]++;
        for(auto n:nums){
            if(cut[n]<=0)
                continue;
            cut[n]--;
            if(tail[n-1]){
                tail[n-1]--;
                tail[n]++;
            }else if(cut[n+1]&&cut[n+2]){ 
                cut[n+1]--;cut[n+2]--;
                tail[n+2]++;
            }else
                return false;
        }
        return true;
    }
};

algorithm analysis

two-pass解决问题，时间复杂度O(n).hashmap插入操作时间也是O(1)。