What is the key pattern in solving the 'Split Array into Consecutive Subsequences' problem?

The key pattern involves using a greedy approach with a hash map to track subsequences and their lengths, ensuring the conditions for consecutive subsequences are met.

Can this problem be solved without a hash map?

While it's possible to use other data structures, a hash map offers the most efficient way to track subsequences and their lengths during the greedy process.

What happens if subsequences can't be formed?

If it's impossible to extend or create a valid subsequence, the solution will return `false`.

How does array scanning apply in the 'Split Array into Consecutive Subsequences' problem?

Array scanning is used to check each element sequentially and determine whether it can be added to an existing subsequence or start a new one, ensuring the conditions for consecutive subsequences are met.

What are the time and space complexities for the solution?

The time complexity is O(n) because the algorithm scans through the array once, and the space complexity is O(n) due to the hash map used to track subsequences.

#659

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

分割数组为连续子序列

给你一个按非递减顺序排列的整数数组 nums 。请你判断是否能在将 nums 分割成一个或多个子序列的同时满足下述两个条件：每个子序列都是一个连续递增序列（即，每个整数恰好比前一个整数大 1 ）。所有子序列的长度至少为 3 。如果可以分割 nums 并满足上述条件，则…

数组哈希表贪心堆（优先队列）

题目描述

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述两个条件：

每个子序列都是一个 连续递增序列（即，每个整数恰好比前一个整数大 1 ）。
所有子序列的长度至少为 3 。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

提示：

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000
nums 按非递减顺序排列

lightbulb

解题思路

方法一：哈希表 + 优先队列（小根堆）

由于题目中的子序列是由连续整数组成的，因此，只要知道子序列的最后一个数以及子序列的长度，就能够确定子序列。

我们可以使用哈希表存储每个子序列的最后一个数，使用优先队列存储当前数作为子序列的末尾时，子序列的长度。我们要优先选择长度较短的子序列，因此使用小根堆。

遍历数组 nums，对于当前遍历到的数 num，如果 num 不能加入到任何子序列中，那么我们就创建一个新的子序列，长度为 1；否则，我们就将 num 加入到某个子序列中，具体的子序列是哪个呢？我们可以从 num - 1 对应的子序列中取出一个长度最短的子序列，将 num 加入到该子序列中，然后将该子序列的最后一个数更新为 num，同时将该子序列的长度加 1。

如果我们遍历完数组 nums，优先队列中所有的子序列的长度都不小于 3，那么我们就可以将数组 nums 分割成若干个子序列，否则，我们就无法将数组 nums 分割成若干个子序列。

时间复杂度 $O(n\log n)$ ，其中 $n$ 是数组 nums 的长度。空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        d = defaultdict(list)
        for v in nums:
            if h := d[v - 1]:
                heappush(d[v], heappop(h) + 1)
            else:
                heappush(d[v], 1)
        return all(not v or v and v[0] > 2 for v in d.values())

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate is familiar with greedy strategies and hash map usage.
question_mark
Candidate shows understanding of array scanning techniques and subsequence formation.
question_mark
Candidate demonstrates the ability to optimize solutions using map-based lookups.

warning

常见陷阱

外企场景

error
Not checking for valid subsequences before creating new ones.
error
Incorrectly updating the hash map, causing invalid subsequences.
error
Forgetting to handle cases where no subsequence can be formed for certain elements.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow subsequences of length 2 or more instead of 3.
arrow_right_alt
Introduce additional constraints such as distinct integers in the array.
arrow_right_alt
Alter the problem to find the smallest subsequence possible instead of focusing on consecutive subsequences.

help

常见问题

外企场景

继续练习

#632 最小区间 #621 任务调度器 #1054 距离相等的条形码