659. Split Array into Consecutive Subsequences

659. Split Array into Consecutive Subsequences

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

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

Note:

1. The length of the input is in range of [1, 10000]

------------------------
第一次遍历计算出每一个数的个数
第二次遍历，每一个数都有2种可能
1. 插入之前某个连
2. 重新开一个连
贪心，每次都先选择1

needed用来保存现有的连的末尾

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> frq = new HashMap<>();
        Map<Integer, Integer> needed = new HashMap<>();
        for (int n : nums) {
            frq.put(n, frq.getOrDefault(n, 0) + 1);
        }
        
        for (int n : nums) {
            if (frq.get(n) == 0) continue;
            if (needed.getOrDefault(n,0) > 0) {
                needed.put(n, needed.get(n) - 1);
                needed.put(n + 1, needed.getOrDefault(n + 1, 0) + 1);
            }else if (frq.getOrDefault(n + 1, 0) > 0 
                      && frq.getOrDefault(n + 2, 0) > 0) {
                
                frq.put(n + 1, frq.get(n + 1) - 1);
                frq.put(n + 2, frq.get(n + 2) - 1);
                needed.put(n + 3, needed.getOrDefault(n + 3, 0) + 1);
            }else {
                return false;
            }
            
            frq.put(n, frq.get(n) - 1);
        }
        
        return true;
    }
}

ToDo 其他解法
https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106495/Java-O(n)-time-and-O(1)-space-solution-greedily-extending-shorter-subsequence