LeetCode 题解工作台
美丽子集的数目
给你一个由正整数组成的数组 nums 和一个 正 整数 k 。 如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。 返回数组 nums 中 非空 且 美丽 的子集数目。 nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数…
7
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用哈希表或数组 记录当前已经选择的数字以及它们的个数，用 记录美丽子集的数目，初始时 $\textit{ans} = -1$，表示排除空集。 对于数组 中的每个数字 ，我们有两种选择：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。
返回数组 nums 中 非空 且 美丽 的子集数目。
nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。
示例 1：
输入：nums = [2,4,6], k = 2 输出：4 解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。 可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
示例 2：
输入：nums = [1], k = 1 输出：1 解释：数组 nums 中的美丽数组有：[1] 。 可以证明数组 [1] 中只存在 1 个美丽子集。
提示：
1 <= nums.length <= 181 <= nums[i], k <= 1000
解题思路
方法一：计数 + 回溯
我们用哈希表或数组 记录当前已经选择的数字以及它们的个数，用 记录美丽子集的数目，初始时 ，表示排除空集。
对于数组 中的每个数字 ，我们有两种选择：
- 不选择 ，此时直接递归到下一个数字；
- 选择 ，此时需要判断 和 是否已经在 中出现过，如果都没有出现过，那么我们就可以选择 ，此时我们将 的个数加一，然后递归到下一个数字，最后将 的个数减一。
最后，我们返回 即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
def dfs(i: int) -> None:
nonlocal ans
if i >= len(nums):
ans += 1
return
dfs(i + 1)
if cnt[nums[i] + k] == 0 and cnt[nums[i] - k] == 0:
cnt[nums[i]] += 1
dfs(i + 1)
cnt[nums[i]] -= 1
ans = -1
cnt = Counter()
dfs(0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \log n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for use of sorting plus hash table to avoid O(n^2) pair checks.
- question_mark
Check whether subsets are counted without missing any edge cases with difference k.
- question_mark
Verify handling of small arrays and duplicates using the hash table.
常见陷阱
外企场景- error
Counting subsets without checking the absolute difference k for all pairs.
- error
Failing to handle duplicate numbers, leading to overcounting.
- error
Recursing without pruning invalid branches, causing unnecessary computation.
进阶变体
外企场景- arrow_right_alt
Count beautiful subsets with at most one pair violating the k difference.
- arrow_right_alt
Find all beautiful subsets where the difference must not be a multiple of k.
- arrow_right_alt
Return the sum of elements in all beautiful subsets instead of the count.