題目

給你一個整數陣列 nums 和一個正整數 k，請你判斷是否可以把這個陣列劃分成一些由 k 個連續數字組成的集合。

如果可以，請返回 True；否則，返回 False。

注意：此題目與 846 重複

示例 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]。

示例 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。

解題思路分析

1、排序遍歷；時間複雜度O(nlog(n))，空間複雜度O(1)

func isPossibleDivide(nums []int, k int) bool {	n := len(nums)	if n%k != 0 {		return false	}	if k == 1 {		return true	}	sort.Ints(nums)	for i := 0; i < n; i++ {		if nums[i] >= 0 {			count := 1			for j := i + 1; j < n; j++ {				if nums[j] > nums[i]+count {					break				}				if nums[j] >= 0 && nums[j] == nums[i]+count {					nums[j] = -1					count++					if count == k {						break					}				}			}			if count != k {				return false			}			nums[i] = -1		}	}	return true}

2、雜湊輔助；時間複雜度O(nlog(n))，空間複雜度O(n)

func isPossibleDivide(nums []int, k int) bool {	n := len(nums)	if n%k != 0 {		return false	}	if k == 1 {		return true	}	arr := make([]int, 0)	m := make(map[int]int)	for i := 0; i < len(nums); i++ {		if m[nums[i]] == 0 {			arr = append(arr, nums[i])		}		m[nums[i]]++	}	sort.Ints(arr)	for i := 0; i < len(arr); i++ {		if m[arr[i]] > 0 {			for j := 1; j < k; j++ {				value := arr[i] + j				m[value] = m[value] - m[arr[i]]				if m[value] < 0 {					return false				}			}		}	}	return true}

3、雜湊輔助；時間複雜度O(nlog(n))，空間複雜度O(n)

func isPossibleDivide(nums []int, k int) bool {	n := len(nums)	if n%k != 0 {		return false	}	if k == 1 {		return true	}	m := make(map[int]int)	for i := 0; i < len(nums); i++ {		m[nums[i]]++	}	sort.Ints(nums)	for i := 0; i < len(nums); i++ {		value := m[nums[i]]		if value > 0 {			for j := 0; j < k; j++ {				if m[nums[i]+j] < value {					return false				}				m[nums[i]+j] = m[nums[i]+j] - value			}		}	}	return true}

總結

Medium題目，題目同leetcode846.一手順子