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

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

给你一个整数数组 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]。

method

先排序，统计每个数字出现的次数

从左到右遍历，每次遍历到一个数字，如果没被用过，即mp[nums[i]]>0，就去找[nums[i], nums[i]+k-1]这个区间中的数字是否都出现过，如果出现就对应哈希值减一，表示已经用了，如果没出现就说明不能组成连续集合，直接返回

bool isPossibleDivide(vector<int>& nums, int k) {
    int n = nums.size();
    if (n % k != 0) return false;
    sort(nums.begin(), nums.end());
    unordered_map<int, int> mp;
    for (auto n : nums) mp[n]++;
    for (int i = 0; i < n; i++) {
        if (mp.find(nums[i]) == mp.end()) continue;
        for (int j = nums[i]; j < nums[i] + k; j++) {
            if (mp.find(j) == mp.end()) {
                return false;
            }
            if (--mp[j] == 0) mp.erase(j);
        }
    }
    return true;
}