Leecode --- Split Array into Consecutive Subsequences
===

## Description

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
All subsequences have a length of 3 or more.
Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

input為以升序之數列(ascending order),判斷是否能切成數組子數列,其中子數列的條件為長度大於等於3,且每個數字必須是連續的(e.g 1,3,4為非法的),能完成回傳true,否則false

### Examples

* Ex1:
**Input:** nums = [1,2,3,3,4,5]
**Output**: true
**Explanation**: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

* Ex2:
**Input**: nums = [1,2,3,3,4,4,5,5]
**Output**: true
**Explanation**: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

* Ex3:
**Input**: nums = [1,2,3,4,4,5]
**Output**: false
**Explanation**: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

### Constraints

* 1 <= nums.length <= 10^4^
* -1000 <= nums[i] <= 1000
* nums is sorted in non-decreasing order.

## Solution

The key idea is as possible as to become a safe state with a length greather than 3.If there is additional performance,expand the consecutive subsequence.

First of all,we allocate an array named table,which represents the number of length of each subsquences,table[0] represents number of subsquences of length one,table[1] represents number of subsquences of length two,table[2] indicates number of subsquences of greater or equal to three,among them,only table[2] is in a safe state.If table[0] or table[1] is not zero before the end of procedure,the input is gonna fail and return false.

Another key factor is the repeated of number,only these stuffs will make the answers have various combinations.

So,depend on our ideas,we excute from the first to the last and determine each number of repetitions of the array.Finally,we figure out a way to how the table changes.

For Example: input data :[1,1,2,2,3,3,3,3,3,3,4,4,4,4,5,5,5]

              length:      1       2        3+ 
                     table[0] table[1] table[2]
initial                    0       0        0

start:
1 1                        2       0        0
2 2 2                      1       2        0
3 3 3 3 3 3                3       1        2
- - 4 4 4 4                0       3        1      can't extend be (1,2,3,4) because the salvations are first
- - - 5 5 5                0       0        0  
      

### implement code

import java.util.*;
class Solution {
    public boolean isPossible(int[] nums) {
        int[] table = new int[]{0,0,0};
          //table[0] speaks its length =1
          //table[1] speaks its length =2
          //table[2] speaks its length =3+
        int pointer = 0;
        boolean init =true;
        while(pointer <nums.length)
        {
            int cur = nums[pointer];
            int pre =0;
            if(init !=true)
                pre = nums[pointer-1];
           
            int numberofcur = numberof(nums,pointer);
            pointer += numberofcur;
            
            if(cur != pre+1 && init !=true)
            {
                if(table[0] != 0 || table[1] != 0)
                    return false;
                table[2] =0;
            }
            if((table[0] + table[1] ) >numberofcur)
                return false;
            int tmp = table[2];
            numberofcur -= (table[1] +table[0]);
            table[2] = table[1];
            table[1] =table[0];
          
            if(numberofcur ==0 || tmp ==0 )
                table[0] =numberofcur;
            else if(tmp >= numberofcur)
            {
                table[2] += numberofcur;
                table[0] =0;                
            }
            else
            {
                table[2] += tmp;
                table[0] = numberofcur-tmp;
            } 
            init =false;
        }
        if(table[0] !=0 || table[1] != 0)
            return false;
        return true;
    }
    private int numberof(int[]nums,int pointer)
    {
        int i =pointer;
        while(i<nums.length)
        {
            if(nums[pointer] != nums[i])
            {
                return i-pointer;
            }
            i++;
        }
        return i- pointer ;
        
    }
}

**function** numberof :
to determine how many the repetition of specific data

**line 20~25:** If it is not consecutive number in two continuous indices of the array,we'll determine if the new restart can be used and clear the table

**line 26** : It's accelerate operation .

**line 29~31** : How to rescue? It is a subsequence of one to two lengths or two to three lengths,numberofcur is representing what its ability,table[0] to table[1] or table[1] to table[2] are the act of salvation.

**line 33~44** : Determine whether there is remaining expansion capacity.

#### Submission on leetcode:

Runtime: **1 ms, faster than 100.00%** of Java online submissions for Split Array into Consecutive Subsequences.
Memory Usage: **39.9 MB, less than 90.57%** of Java online submissions for Split Array into Consecutive Subsequences.

#### Time complexity

walking around the each element in input array,
=>==O(n) , which n is input array's size.==

## Conclusion

It's similar to a poker game ,I'll dertermine wheater my cards can make a couple of straights.

that's a hard problem ,I'll give it four stars.

==★★★★☆==

###### tags: `Leetcode` `Medium`