# 659.Split-Array-into-Consecutive-Subsequences

## 题目地址

https://leetcode.com/problems/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

Constraints:
1 <= nums.length <= 10000``````

## 代码

### Appraoch #2 Greedy Fréquence HashMap

``````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) {
// freq[i]不为零，可以追加到子列
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;
}``````

### Approach #2 Greedy

Say we have a count of each number, and let `tails[x]` be the number of chains ending right before `x`.

Time: O(N) && Space: O(N)

``````class Solution {
public boolean isPossible(int[] nums) {
Counter count = new Counter();
Counter tails = new Counter();
for (int x: nums)        count.add(x, 1);

for (int x: nums) {
if (count.get(x) == 0) {
continue;
} else if (tails.get(x) > 0) {
} else if (count.get(x+1) > 0 && count.get(x+2) > 0) {
} else {
return false;
}
}
return true;
}
}

class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}

public void add(int k, int v) {
put(k, get(k) + v);
}
}``````

### Approach #1 Opening and Closing Events

Time: O(N) && Space: O(N)

``````class Solution {
public boolean isPossible(int[] nums) {
Integer prev = null;
int prevCount = 0;
Queue<Integer> starts = new LinkedList();
int anchor = 0;

for (int i = 0; i < nums.length; i++) {
int t = nums[i];
if (i == nums.length - 1 || nums[i+1] != t) {
int count = i - anchor + 1;
if (prev != null && t - prev != 1) {
while (prevCount-- > 0) {
if (prev < starts.poll() + 2)     return false;
prev = null;
}
}

if (prev == null || t - prev == 1) {
while (prevCount > count) {
prevCount--;
if (t-1 < starts.poll() + 2)     return false;
}
while (prevCount++ < count) {
}
}
prev = t;
preCount = count;
anchor = i + 1;
}
}

while (prevCount-- > 0) {
if (nums[nums.length - 1] < starts.poll() + 2)     return false;
}

return true;
}
}``````

Last updated