659. Split Array into Consecutive Subsequences

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)

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