leetcode#659 分割数组为连续子序列

4. 分割数组为连续子序列

659. 分割数组为连续子序列

给你一个按升序排序的整数数组 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

解题思路：

右转评论区大佬

作者：Arsenal-591
链接：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/solution/tan-xin-o1-kong-jian-fu-za-du-de-zui-you-jie-fa-by/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

func isPossible(nums []int) bool {
	dp1, dp2, dp3 := 0, 0, 0 // 分别记录长度1，2，3连续子序列 个数

	for i := 0; i < len(nums); {
		start := i
		x := nums[i]

		for i < len(nums) && nums[i] == x {
			i++
		}

		cnt := i - start

    // 不比prev大1，
		if start > 0 && x != nums[start-1]+1 {
			if dp1+dp2 > 0 { // 并且存在1，2长度的，1，2长度的子序列一定不能再连续了
				return false
			} else {
				dp1 = cnt
				dp2 = 0 // dp2一定是0，因为大于0的情况，上面已经返回了，此置零可以省去
				dp3 = 0 // 大于3，符合要求  置零
			}
		} else {
			if dp1+dp2 > cnt {
				return false
			}
			leave := cnt - dp1 - dp2
			keep := dp3
			if leave < dp3 {
				keep = leave
			}
			dp3 = keep + dp2 //可以继续加的
			dp2 = dp1
			dp1 = leave - keep // 剩下的
		}
	}
	return dp1 == 0 && dp2 == 0
}

leetcode#659 分割数组为连续子序列

原文：https://www.cnblogs.com/iQXQZX/p/14087436.html