老晨Leetcode 659 分割数组为连续子序列 · Split Array into Consecutive Subsequences

给定一个整数数组 nums. 现在需要将 nums 拆分成若干个 (至少1个) 子序列, 并且每个子序列至少包含 3 个连续的整数.
返回是否能做到这样的拆分.

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
本题贪心的思路不是那么容易想到
我们首先先把每个数出现的次数存起来放在 count map里
然后把已经成形的sequence （>=3）存起来 （只需要存最后可以放在结尾的数，比如说已经有123了，下一个我可以放4，那就把4作为key）
有可能是112233， 可以放两个4， 所以tail map存的是 ：
key: 下一个能放哪个数
value: 能放几个这个数

遍历每个数的时候，
1.如果这个数已经用完了，就跳过
2.如果可以加到已经成型的sequence，就加上
3.如果加不进去，再试着以这个数为开头，把n+1, n+2也都找到，组成一个序列
(每次组序列的时候，都要满足3个才行)
4.都不满足，就return false

public boolean isPossible(int[] a) {
        Map<Integer, Integer> count = new HashMap();// num -> count
        Map<Integer, Integer> tail = new HashMap();// tail -> how many this tail are needed
        for(int i = 0; i < a.length; i++) {
            int cur = count.getOrDefault(a[i], 0);
            count.put(a[i], cur+1);
        } 
        for(int i = 0; i < a.length; i++) {
            if(count.get(a[i]) <= 0) continue;
            if(tail.getOrDefault(a[i], 0) > 0) {
                tail.put(a[i], tail.get(a[i]) - 1);
                tail.put(a[i]+1, tail.getOrDefault(a[i]+1,0) +1);                
            } else if(count.getOrDefault(a[i]+1,0) > 0 && count.getOrDefault(a[i]+2,0) >0) {
                count.put(a[i]+1, count.get(a[i]+1) - 1);
                count.put(a[i]+2, count.get(a[i]+2) - 1);
                tail.put(a[i]+3, tail.getOrDefault(a[i]+3,0) + 1);
            } else {
                return false;
            }
            count.put(a[i], count.get(a[i]) - 1);
        }
        return true;
    }