LeetCode 题解工作台
好分区的数目
给你一个正整数数组 nums 和一个整数 k 。 分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。 返回 不同 的好分区的数目。由于答案可能很大，请返回对 10 9 + 7 取余 后的结果。 …
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
对于一个长度为 的数组 `nums`，每个元素都可以选择放入第一个分区或第二个分区，因此一共有 种分区方式。每一种分区方式，得到的结果可以是“好分区”或者“坏分区”，题目要我们求“好分区”的个数，我们可以转换为求“坏分区”的个数。那么“好分区”的个数就是 减去“坏分区”的个数。 “坏分区”实际上就是从数组 `nums` 中选出若干个元素，使得这若干个元素之和不超过 。这可以通过动态规划（0-…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
示例 1：
输入：nums = [1,2,3,4], k = 4 输出：6 解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
示例 2：
输入：nums = [3,3,3], k = 4 输出：0 解释：数组中不存在好分区。
示例 3：
输入：nums = [6,6], k = 2 输出：2 解释：可以将 nums[0] 放入第一个分区或第二个分区中。 好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
提示：
1 <= nums.length, k <= 10001 <= nums[i] <= 109
解题思路
方法一：逆向思维 + 动态规划
对于一个长度为 的数组 nums，每个元素都可以选择放入第一个分区或第二个分区，因此一共有 种分区方式。每一种分区方式，得到的结果可以是“好分区”或者“坏分区”，题目要我们求“好分区”的个数，我们可以转换为求“坏分区”的个数。那么“好分区”的个数就是 减去“坏分区”的个数。
“坏分区”实际上就是从数组 nums 中选出若干个元素，使得这若干个元素之和不超过 。这可以通过动态规划（0-1 背包问题）来求解。
我们用 表示从数组 nums 的前 个元素中选出若干个元素，使得这若干个元素之和为 的方案数。那么 的状态转移方程为：
那么“坏分区”的个数就是 ，其中 为数组 nums 的长度。最后，我们用 减去“坏分区”的个数，即可得到“好分区”的个数。
时间复杂度 ，空间复杂度 。其中 为数组 nums 的长度，而 为整数 。
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
if sum(nums) < k * 2:
return 0
mod = 10**9 + 7
n = len(nums)
f = [[0] * k for _ in range(n + 1)]
f[0][0] = 1
ans = 1
for i in range(1, n + 1):
ans = ans * 2 % mod
for j in range(k):
f[i][j] = f[i - 1][j]
if j >= nums[i - 1]:
f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod
return (ans - sum(f[-1]) * 2 + mod) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the array length and k, typically O(n*k) for DP updates. Space complexity is O(k) for storing feasible subset sums, optimized by using rolling arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate recognizes the sum threshold failure mode when total sum is less than 2*k.
- question_mark
Candidate proposes DP state representing subset sums rather than brute force enumeration.
- question_mark
Candidate considers modulo arithmetic to manage large output and prevent overflow errors.
常见陷阱
外企场景- error
Failing to account for the sum < 2*k edge case leads to incorrect zero partitions.
- error
Double counting subsets if state transitions are not carefully handled.
- error
Ignoring the modulo operation can cause integer overflow on large arrays.
进阶变体
外企场景- arrow_right_alt
Count partitions into three groups each with sum at least k.
- arrow_right_alt
Find great partitions when order of elements in each group does not matter.
- arrow_right_alt
Calculate partitions with sum exactly equal to k instead of at least k.