> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/greedy/659.-split-array-into-consecutive-subsequences.md).

# 659. Split Array into Consecutive Subsequences

![](/files/-MhckwnKyGIwr8m4M-PX)

![](/files/-Mhckz7JbnCWR6D2hQik)

![](/files/-MiBB6QnXkKWcBs5K_SH)

want to find CIS, 

but make sure it's cis and length >= 3, make sure num, num+1, num+2 exists in the following nums

count: map\[number, freq count => how many keys not checked]

canAppend: map\[append From Which number Ending, how many subsequence has created]

ex: 1 1 2 2 3 3 4

#### 1. 創立新的 subsequnce

起始 by 某數 x, 那要確保 x+1, x+2 都成立

ex: 起始 by 1, 那 2 3 都確保有用, count—

1 x x 2 x x 3

#### 2. append from 某 subseq

1 x x 2 x x 3 xxxx \[4], 假設已經有既有的 subsequence, 後面直接接上

why append, 為什麼不重啟一個新的 subsequence ⇒ 因為 直接 append 可以確保一定成功, 重啟一個新的 , 還要確定後面有 5, 6

```
if (canAppend.getOrDefault(num-1, 0) > 0) {
    canAppend.put(num-1, canAppend.get(num-1)-1);
    canAppend.put(num, canAppend.getOrDefault(num, 0) + 1);
```

如果 current num 前面的數字, 有既有的 subsequence, 那可以拿來繼續拼接,

所以變成

canAppend\[num-1]—;

canAppend\[num]++,

如果都沒有既有的 subsequnce 存在, 那就要做 1. ⇒ 創立新的 subsequnce

```
} else { // start by num
    if (count.getOrDefault(num+1, 0) == 0 || count.getOrDefault(num+2, 0) == 0) {
        return false;
    }
    count.put(num+1, count.get(num+1)-1); // num+1 用過--
    count.put(num+2, count.get(num+2)-1); // num+2 用過--
    canAppend.put(num+2, canAppend.getOrDefault(num+2, 0) + 1);
}
```

```
// 如此, 在 num+2, 有既有的 subsequnce ++
canAppend.put(num+2, canAppend.getOrDefault(num+2, 0) + 1);
```

time: O(n)

space:O(n)

```java
class Solution {
    public boolean isPossible(int[] nums) {
        /*
            0. count[x] == 0 continue; 
            1. start by x, x+1, x+2, used, count--, canAppend[x+2]++
            2. canAppend[x-1] > 0, means we can append by before subsequence, canAppend[x-1]--. canAppend[x]++
        */
        Map<Integer, Integer> count = new HashMap<>(); // map[number, freq count => how many keys not checked]
        Map<Integer, Integer> canAppend = new HashMap<>(); // map[append From Which number Ending, how many subsequence has created]
        
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        for (int num : nums) {
            if (count.get(num) == 0) continue;
            
            count.put(num, count.get(num)-1);
            
            if (canAppend.getOrDefault(num-1, 0) > 0) {
                canAppend.put(num-1, canAppend.get(num-1)-1);
                canAppend.put(num, canAppend.getOrDefault(num, 0) + 1);
                
            } else { // start by num
                if (count.getOrDefault(num+1, 0) == 0 || count.getOrDefault(num+2, 0) == 0) {
                    return false;
                }
                count.put(num+1, count.get(num+1)-1);
                count.put(num+2, count.get(num+2)-1);
                canAppend.put(num+2, canAppend.getOrDefault(num+2, 0) + 1);
            }

        }
        return true;
        
    }
}
```