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: TrueExplanation:You can split them into two consecutive subsequences : 1, 2, 33, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]Output: TrueExplanation:You can split them into two consecutive subsequences : 1, 2, 3, 4, 53, 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]

 

优先把当前的元素放进更短的的数组里（贪心）。

第一次遍历数组：统计频率。

第二次遍历数组：检查当前元素nums[i]是否能加入到现有的数组后面（是否存在以当前元素nums[i] - 1结尾的数组，如果有，加入到长度最短的数组里）；如果没有，检查能否创建以该元素开头的新数组；若两种情况都不符合，返回false

detail：用两个hashmap，freq和map，map表示序列以某元素结尾。第二次遍历数组时，如果当前元素nums[i]在map中的key > 0，说明该元素能加入到现有的数组后面；如果当前元素nums[i]在map中不存在，检查该元素接下来连续的两个数字在freq中的value是否 > 0，都大于0说明可以以该元素开头的新数组，在freq中对应key的value减1，并在map中加入consecutive的第三个数字，表示这个数组的末尾，以备下次检查数组元素能否加入到现有数组后面。如果以上两种情况都不符合，返回false。

例如<1,2,3,3,4,5>，

时间：O(N)，空间：O(N)

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