腾讯&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