腾讯&leetcode659：分割数组为连续子序列

[sisterAn]

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

示例 1：

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5

示例 2：

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3, 4, 5
3, 4, 5

示例 3：

输入: [1,2,3,4,4,5]
输出: False

提示：

• 输入的数组长度范围为 [1, 10000]

leetcode

[sisterAn]

解法：贪心算法

从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为3），剔除之后，依次往后遍历：

• 判断当前元素是否能够拼接到前一个满足条件的连续子序列上，可以的话，则拼接
• 如果不可以，则判断以当前元素开始能否构成连续子序列（长度为3），可以的话，则剔除连续子序列
• 否则，返回 false

const isPossible = function(nums) {
   let max = nums[nums.length - 1]
   // arr：存储原数组中数字每个数字出现的次数
   // tail：存储以数字num结尾的且符合题意的连续子序列个数
   let arr = new Array(max + 2).fill(0), 
       tail = new Array(max + 2).fill(0)
   for(let num of nums) {
       arr[num] ++
   }
   for(let num of nums) {
       if(arr[num] === 0) continue
       else if(tail[num-1] > 0){
           tail[num-1]--
           tail[num]++
       }else if(arr[num+1] > 0 && arr[num+2] > 0){
           arr[num+1]--
           arr[num+2]--
           tail[num+2]++
       } else {
           return false
       }
       arr[num]--
   }
   return true
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

leetcode