LeetCode 题解工作台
从一个范围内选择最多整数 I
给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数： 被选择整数的范围是 [1, n] 。 每个整数 至多 选择 一次 。 被选择整数不能在数组 banned 中。 被选择整数的和不超过 maxSum 。 请你返回按照上述规则 最多 可以选择的整数数目…
5
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用变量 表示当前已经选择的整数的和，用变量 表示当前已经选择的整数的个数。将数组 `banned` 转换为哈希表，方便判断某个整数是否不可选。 接下来，我们从 开始枚举整数 ，如果 $s + i \leq maxSum$ 且 不在 `banned` 中，那么我们就可以选择整数 ，并将 和 分别加上 和 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：
- 被选择整数的范围是
[1, n]。 - 每个整数 至多 选择 一次 。
- 被选择整数不能在数组
banned中。 - 被选择整数的和不超过
maxSum。
请你返回按照上述规则 最多 可以选择的整数数目。
示例 1：
输入：banned = [1,6,5], n = 5, maxSum = 6 输出：2 解释：你可以选择整数 2 和 4 。 2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
示例 2：
输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1 输出：0 解释：按照上述规则无法选择任何整数。
示例 3：
输入：banned = [11], n = 7, maxSum = 50 输出：7 解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。 它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。
提示：
1 <= banned.length <= 1041 <= banned[i], n <= 1041 <= maxSum <= 109
解题思路
方法一：贪心 + 枚举
我们用变量 表示当前已经选择的整数的和，用变量 表示当前已经选择的整数的个数。将数组 banned 转换为哈希表，方便判断某个整数是否不可选。
接下来，我们从 开始枚举整数 ，如果 且 不在 banned 中，那么我们就可以选择整数 ，并将 和 分别加上 和 。
最终，我们返回 即可。
时间复杂度 ，空间复杂度 。其中 为给定的整数。
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
ans = s = 0
ban = set(banned)
for i in range(1, n + 1):
if s + i > maxSum:
break
if i not in ban:
ans += 1
s += i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m + n) where m is the length of banned, due to building the hash set and scanning the range. Space complexity is O(m) for storing banned numbers in the hash set. |
| 空间 | O(m) |
面试官常问的追问
外企场景- question_mark
Checking whether candidate numbers fall in banned set.
- question_mark
Evaluating cumulative sum to avoid exceeding maxSum.
- question_mark
Expecting a greedy selection from smallest to largest integers.
常见陷阱
外企场景- error
Forgetting to exclude banned numbers greater than n.
- error
Adding numbers until maxSum is exceeded instead of stopping before.
- error
Not using a hash set, leading to O(n*m) time complexity.
进阶变体
外企场景- arrow_right_alt
Allow negative numbers in the range and adjust sum constraints accordingly.
- arrow_right_alt
Select numbers with replacement to maximize the count under maxSum.
- arrow_right_alt
Optimize for multiple queries with different maxSum values over the same banned list.