# 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]

``````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;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/659

Top K Frequent Words

https://leetcode.com/problems/split-array-into-consecutive-subsequences/

https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106496/Java-O(n)-Time-O(n)-Space

https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106493/C%2B%2B-O(n)-solution-two-pass

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

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation