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

难度：中等

题目

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

示例

示例一：

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

示例二：

输入：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]。

示例三：

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

示例四：

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

提示

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

解题

首先对长度进行过滤，如果数组长度不是数组的整数倍，直接返回 false

然后用 HashMap 将数组存储起来

对数组按照从小到大排序，并开始遍历

当一个数 x 存在，那么 x+1, x+2, … x+k-1 也一定存在

按照这个顺序进行判断，首先判断 x 是否存在，然后循环判断 x 后 k 位是否存在，存在则从 HashMap 中减去一位，否则返回 false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean isPossibleDivide(int[] nums, int k) {
  int n = nums.length;
  if (n%k!=0){
    return false;
  }
  Arrays.sort(nums);
  HashMap<Integer, Integer> map = new HashMap<>();
  for (int num: nums){
    map.put(num, map.getOrDefault(num,0)+1);
  }
  for (int i=0; i<n; i++){
    if (!map.containsKey(nums[i])){
      continue;
    }
    for (int j=0; j<k; j++){
      int num = nums[i]+j;
      if (!map.containsKey(num)){
        return false;
      }
      map.put(num,map.get(num)-1);
      if (map.get(num)==0){
        map.remove(num);
      }
    }
  }
  return true;
}