# 1296. Divide Array in Sets of K Consecutive Numbers

Given an array of integers `nums` and a positive integer `k`, check whether it is possible to divide this array into sets of `k` consecutive numbers.

Return `true`  if it is possible. Otherwise, return `false`.

Example 1:

``````Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
``````

Example 2:

``````Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
``````

Example 3:

``````Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.
``````

Constraints:

• `1 <= k <= nums.length <= 105`
• `1 <= nums[i] <= 109`

Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

``````class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
int n = nums.size();
if (n % k != 0) return false;
map<int, int> numCnt;
for (int num : nums) ++numCnt[num];
for (int i = 0; i < n / k; ++i) {
int start = numCnt.begin()->first;
for (int j = start; j < start + k; ++j) {
if (--numCnt[j] < 0) return false;
if (numCnt[j] == 0) numCnt.erase(j);
}
}
return true;
}
};
``````

``````class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
int n = nums.size();
if (n % k != 0) return false;
map<int, int> numCnt;
for (int num : nums) ++numCnt[num];
for (auto &a : numCnt) {
if (a.second <= 0) continue;
int start = a.first, freq = a.second;
for (int i = 0; i < k; ++i) {
numCnt[start + i] -= freq;
if (numCnt[start + 1] < 0) return false;
}
}
return true;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1296

Hand of Straights

Split Array into Consecutive Subsequences

All Divisions With the Highest Score of a Binary Array

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/discuss/457569/C%2B%2B-Greedy

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/discuss/470238/JavaC%2B%2BPython-Exactly-Same-as-846.-Hand-of-Straights

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation