# [LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列

2021年09月15日 阅读数：1

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.html

Example 1:java

```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:python

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

Java:this

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

Python:url

```# Time:  O(n)
# Space: O(1)
class Solution(object):
def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
pre, cur = float("-inf"), 0
cnt1, cnt2, cnt3 = 0, 0, 0
i = 0
while i < len(nums):
cnt = 0
cur = nums[i]
while i < len(nums) and cur == nums[i]:
cnt += 1
i += 1

if cur != pre + 1:
if cnt1 != 0 or cnt2 != 0:
return False
cnt1, cnt2, cnt3 = cnt, 0, 0
else:
if cnt < cnt1 + cnt2:
return False
cnt1, cnt2, cnt3 = max(0, cnt - (cnt1 + cnt2 + cnt3)), \
cnt1, \
cnt2 + min(cnt3, cnt - (cnt1 + cnt2))
pre = cur
return cnt1 == 0 and cnt2 == 0
```

Python:htm

```def isPossible(self, nums):
left = collections.Counter(nums)
end = collections.Counter()
for i in nums:
if not left[i]: continue
left[i] -= 1
if end[i - 1] > 0:
end[i - 1] -= 1
end[i] += 1
elif left[i + 1] and left[i + 2]:
left[i + 1] -= 1
left[i + 2] -= 1
end[i + 2] += 1
else:
return False
return True　　```

C++:

```class Solution {
public:
bool isPossible(vector<int>& nums)
{
unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> backs;

// Keep track of the number of sequences with size < 3
int need_more = 0;

for (int num : nums)
{
if (! backs[num - 1].empty())
{	// There exists a sequence that ends in num-1
// Append 'num' to this sequence
// Remove the existing sequence
// Add a new sequence ending in 'num' with size incremented by 1
int count = backs[num - 1].top();
backs[num - 1].pop();
backs[num].push(++count);

if (count == 3)
need_more--;
}
else
{	// There is no sequence that ends in num-1
// Create a new sequence with size 1 that ends with 'num'
backs[num].push(1);
need_more++;
}
}
return need_more == 0;
}
};
```

C++:

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