原文链接: https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences

英文原文

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).

 

Example 1:

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

Example 2:

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

Example 3:

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 <= 104
• -1000 <= nums[i] <= 1000
• nums is sorted in non-decreasing order.

中文题目

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

通过代码

高赞题解

算法思路

首先使用两个哈希 mapnc和tail

• nc[i]：存储原数组中数字i出现的次数

• tail[i]：存储以数字i结尾的且符合题意的连续子序列个数

1. 先去寻找一个长度为3的连续子序列 i, i+1, i+2，找到后就将 nc[i], nc[i+1], nc[i+2] 中对应数字消耗1个（即-1），并将 tail[i+2] 加 1，即以 i+2 结尾的子序列个数 +1。

2. 如果后续发现有能够接在这个连续子序列的数字 i+3，则延长以 i+2 为结尾的连续子序列到 i+3，此时消耗 nc[i+3] 一个，由于子序列已延长，因此tail[i+2] 减 1，tail[i+3] 加 1

在不满足上面的情况下

3. 如果 nc[i] 为 0，说明这个数字已经消耗完，可以不管了

4. 如果 nc[i] 不为 0，说明这个数字多出来了，且无法组成连续子序列，所以可以直接返回 false 了

因此，只有检查到某个数时，这个数未被消耗完，且既不能和前面组成连续子序列，也不能和后面组成连续子序列时，无法分割

复杂度分析

• 时间复杂度：$O(N)$，所有元素遍历一遍 $O(N)$，循环内部均为常数时间操作 $O(1)$

• 空间复杂度：$O(N)$，使用了两个哈希 map

举例

以 nums=[1,2,3,3,4,4,5] 为例

1. 初始化：nc[1] = 1、nc[2]=1、nc[3]=2、nc[4]=2、nc[5]=1，tail[i]都为0

2. 检查数字 1, nc[1]>0,并且 nc[2]>0,nc[3]>0，因此找到了一个长度为3的连续子序列 nc[1]、nc[2]、nc[3] 各自减一，并 tail[3] 加 1，此时有

   • nc[1] = 0、nc[2]=0、nc[3]=1、nc[4]=2、nc[5]=1

   • tail[3]=1

3. 检查数字 2，发现 nc[2] 为 0，跳过（已经被消耗完了）

4. 检查数字 3，发现 nc[3]>0,但是 tail[2]=0，因此不能接在前面，只能往后看(如果后面组不成，那就返回 false了),实际发现 nc[4]>0,nc[5]>0，因此找到了一个长度为3的连续子序列 nc[3]、nc[4]、nc[5] 各自减一，并 tail[5] 加 1，此时有

   • nc[1] = 0、nc[2]=0、nc[3]=0、nc[4]=1、nc[5]=0

   • tail[3]=1、tail[5]=1

5. 检查第二个数字 3，nc[3]=0，跳过

6. 检查数字 4，nc[4]>0，又有 tail[3]>0，说明有一个以3结尾的连续子序列，因此可以将其延长，所以nc[4]减1，tail[3]减1,tail[4]加1,此时有

   • nc[1] = 0、nc[2]=0、nc[3]=0、nc[4]=0、nc[5]=0

   • tail[3]=0、tail[4]=1、tail[5]=1

7. 检查数字 5，nc[5]=0，跳过

8. 遍历完所有数字，返回 true

[]

class Solution {

public:

    bool isPossible(vector<int>& nums) {

        unordered_map<int, int> nc, tail;

        for(auto num : nums){

            nc[num]++;

        }

        

        for(auto num : nums){

            if(nc[num] == 0) continue;

            else if(nc[num] > 0 && tail[num-1] > 0){

                nc[num]--;

                tail[num-1]--;

                tail[num]++;

            }else if(nc[num] > 0 && nc[num+1] > 0 && nc[num+2] > 0){

                nc[num]--;

                nc[num+1]--;

                nc[num+2]--;

                tail[num+2]++;

            }else{

                return false;

            }

        }

        return true;

    }

};

如有错误，欢迎评论批评指正

统计信息

通过次数	提交次数	AC比率
28919	53386	54.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
前 K 个高频元素	中等