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:
- The length of the input is in range of [1, 10000]
含义:给定一个升序的数组,要求拆分出多个子数组,子数组至少要有3个元素,且是公差为1的递增序列
1 public boolean isPossible(int[] nums) { 2 Map<Integer, Integer> cards = new HashMap<>(); 3 for (int i : nums) cards.put(i, cards.getOrDefault(i, 0) + 1); 4 Map<Integer, Integer> map = new HashMap<>(); //key是已有的满足规则队列的下一个期待的数,value是满足规则的队列数,大于0才表示队列有效 5 for (int i : nums) { 6 if (cards.get(i) == 0) continue; // 这个数用完了 7 if (map.getOrDefault(i, 0) > 0) { 8 // 加到已经有的队列 9 map.put(i, map.get(i) - 1); 10 map.put(i + 1, map.getOrDefault(i + 1, 0) + 1); 11 } else if (cards.getOrDefault(i + 1, 0) > 0 && cards.getOrDefault(i + 2, 0) > 0) { 12 // 取i,i+1,i+2这三个数,加到新的队列 13 cards.put(i + 1, cards.get(i + 1) - 1); 14 cards.put(i + 2, cards.get(i + 2) - 1); 15 map.put(i + 3, map.getOrDefault(i + 3, 0) + 1); 16 } else return false; // 这个数无处容身 17 cards.put(i, cards.get(i) - 1); 18 } 19 return true; 20 }