题目

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

示例 1：

输入：nums = [1,2,3,3,4,4,5,6], k = 4 输出：tru 解释：数组可以分成 [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]。

示例 3：

输入：nums = [3,3,2,2,1,1], k = 3 输出：true

示例 4：

输入：nums = [1,2,3,4], k = 3 输出：false

解释：数组不能分成几个大小为 3 的子数组。

提示：

1 <= nums.length <= 10^5 1 <= nums[i] <= 10^9 1 <= k <= nums.length

来源：力扣（ LeetCode ）链接： https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解答过程和众评论里的相似，但是看到一个速度排行榜前面大佬的代码我就搞不明白原理了，萌新求指教

大佬的解答过程

class Solution: def isPossibleDivide(self, nums: List[int], k: int) -> bool: n = len(nums) if n % k != 0: return False for i in range(len(nums)): nums[i] %= k lookup = {} for val in nums: if val in lookup: lookup[val] += 1 else: lookup[val] = 1 kn = n // k for i in range(k): if lookup[i] != kn: return False return True

7 条回复 2019-12-30 22:16:14 +08:00

Girlphobia

2019-12-29 20:01:22 +08:00 via Android

有连续的 k 个整数 (a_0, ..., a_(k-1)) ，将每个数对 k 取模，余数必然遍历 0 到(k-1)。比如 [3,4,5,6,7] ，对 5 取模得到 [3,4,0,1,2] 。
那假设一共有 kn 个连续的 k 个整数，每个数列的所有数对 k 取模都有 0 到(k-1)每个数出现正好一次（在 loopkup 里面设置自增），那么在 lookup 里所有的 0 到(k-1)都应该出现 kn 次。
但是这个解法是有漏洞的，如果有 nums=[1,2,3,4,8,6] ，参考解法返回 True 而实际应为 False。

Girlphobia

2019-12-29 20:02:37 +08:00 via Android

@Girlphobia 更正：
nums=[1,2,3,4,8,6], k=3

renmu123

2019-12-29 20:35:08 +08:00

@Girlphobia 明白了，感谢大佬

kiwi95

2019-12-29 20:43:07 +08:00 via iPhone

应该把商也记一遍可以解决 1 楼说的问题

Girlphobia

2019-12-29 20:49:24 +08:00 via Android

@kiwi95 是的，两个字典可解

gbin

2019-12-30 21:52:48 +08:00

一种 nlogn 的解法
统计每个数字出现的次数放在一个 map 中，然后从最小元素开始暴力循环，只要 map 不为空，求得当前最小值 cur, 从 cur 开始，对于任意 0 到 k 满足：
1. cur 存在 map 中 (cur in map)
2. map[cur] 减 1 后，如果 map[cur] 已经为 0 则删除 cur 这个 key
3. cur += 1

若所有组合都满足以上条件则说明可以被划分成多份 k 个连续的子数组，否则不可以。

代码如下：

```
class Solution:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
map = collections.Counter(nums)
while map:
cur = min(map.keys())
for _ in range(k):
if cur not in map:
return False
else:
map[cur] -= 1
if map[cur] == 0:
del map[cur]
cur += 1
return True
```

提交后一遍通过，但是效率有点低，供你讨论 :)
Runtime: 500 ms, faster than 33.77% of Python3 online submissions for Divide Array in Sets of K Consecutive Numbers.
Memory Usage: 27.2 MB, less than 100.00% of Python3 online submissions for Divide Array in Sets of K Consecutive Numbers.

gbin

2019-12-30 22:16:14 +08:00

回复不支持 Markdown，所以排版乱了，可以参考这里 https://0x400.com/2019-12-30-lc-1296-divide-array-in-sets-of-k-consecutive-numbers.html

leetcode 刷题遇到的疑惑 1296. 划分数组为连续数字的集合

题目

大佬的解答过程