Leetcode之Split Array into Consecutive Subsequences

题目：

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

代码：

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