What is the main pattern for solving Divide Array in Sets of K Consecutive Numbers?

The primary pattern is array scanning combined with hash table lookup to efficiently track counts and form consecutive sequences.

Can this approach handle large arrays up to 10^5 elements?

Yes, using a hash map for counts and sorting or min-heap for smallest number selection keeps the algorithm efficient for large inputs.

How do duplicates in the array affect the solution?

Duplicates must be decremented in the frequency map as sequences are formed. Failing to do so can incorrectly report that partitioning is impossible.

What happens if a number is missing in the middle of a consecutive set?

If any required number is missing, the greedy sequence construction fails immediately and the algorithm returns false.

Is sorting necessary for Divide Array in Sets of K Consecutive Numbers?

Sorting helps quickly find the smallest available number to start sequences, but a min-heap or ordered map can be used as an alternative.

#1296

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

划分数组为连续数字的集合

给你一个整数数组 nums 和一个正整数 k ，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。如果可以，请返回 true ；否则，返回 false 。示例 1：输入： nums = [1,2,3,3,4,4,5,6], k = 4 输出： true 解释：数组可以分成 […

数组哈希表贪心排序

题目描述

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
如果可以，请返回 true；否则，返回 false。

示例 1：

输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

示例 2：

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

示例 4：

输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

提示：

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

注意：此题目与 846 重复：https://leetcode.cn/problems/hand-of-straights/

lightbulb

解题思路

方法一：哈希表 + 排序

我们首先判断数组 $\textit{nums}$ 的长度是否能被 $\textit{k}$ 整除，如果不能整除，说明无法将数组划分成若干个长度为 $\textit{k}$ 的子数组，直接返回 $\text{false}$ 。

接下来，我们用一个哈希表 $\textit{cnt}$ 统计数组 $\textit{nums}$ 中每个数字出现的次数，然后对数组 $\textit{nums}$ 进行排序。

然后，我们遍历排序后的数组 $\textit{nums}$ ，对于每个数字 $x$ ，如果 $\textit{cnt}[x]$ 不为 $0$ ，我们枚举 $x$ 到 $x+\textit{k}-1$ 的每个数字 $y$ ，如果 $\textit{cnt}[y]$ 为 $0$ ，说明无法将数组划分成若干个长度为 $\textit{k}$ 的子数组，直接返回 $\text{false}$ 。否则，我们将 $\textit{cnt}[y]$ 减 $1$ 。

遍历结束后，说明可以将数组划分成若干个长度为 $\textit{k}$ 的子数组，返回 $\text{true}$ 。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k:
            return False
        cnt = Counter(nums)
        for x in sorted(nums):
            if cnt[x]:
                for y in range(x, x + k):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to sorting or heap operations, where n is the array length. Hash map lookups for building and updating counts are O(1) each. Space complexity is O(n) to store frequency counts.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks if duplicates affect sequence formation
question_mark
Checks understanding of greedy consecutive construction
question_mark
Observes handling of gaps in the array sequence

warning

常见陷阱

外企场景

error
Failing to decrement counts correctly for duplicates
error
Assuming sorted array without handling missing numbers
error
Using linear search instead of hash map, causing TLE for large n

swap_horiz

进阶变体

外企场景

arrow_right_alt
Partition array into sets of k consecutive odd or even numbers
arrow_right_alt
Allow sequences of length k but with at most one missing number
arrow_right_alt
Return the actual groups instead of boolean result

help

常见问题

外企场景

继续练习

#1338 数组大小减半 #1481 不同整数的最少数目 #1090 受标签影响的最大值