LeetCode 题解工作台
k-avoiding 数组的最小总和
给你两个整数 n 和 k 。 对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。 返回长度为 n 的 k-avoiding 数组的可能的最小总和。 示例 1： 输入： n = 5, k = 4 输出： 18 解释： 设若 k-av…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们从正整数 $i = 1$ 开始，依次判断 是否可以加入数组中，如果可以加入，则将 加入数组中，累加到答案中，然后将 $k - i$ 置为已访问，表示 不能加入数组中。循环直到数组长度为 。 时间复杂度 $O(n + k)$，空间复杂度 $O(n + k)$。其中 为数组长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你两个整数 n 和 k 。
对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。
返回长度为 n 的 k-avoiding 数组的可能的最小总和。
示例 1：
输入：n = 5, k = 4 输出：18 解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。 可以证明不存在总和小于 18 的 k-avoiding 数组。
示例 2：
输入：n = 2, k = 6 输出：3 解释：可以构造数组 [1,2] ，其元素总和为 3 。 可以证明不存在总和小于 3 的 k-avoiding 数组。
提示：
1 <= n, k <= 50
解题思路
方法一：贪心 + 模拟
我们从正整数 开始，依次判断 是否可以加入数组中，如果可以加入，则将 加入数组中，累加到答案中，然后将 置为已访问，表示 不能加入数组中。循环直到数组长度为 。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def minimumSum(self, n: int, k: int) -> int:
s, i = 0, 1
vis = set()
for _ in range(n):
while i in vis:
i += 1
vis.add(k - i)
s += i
i += 1
return s
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the ability to implement a greedy solution that minimizes the sum while maintaining correctness.
- question_mark
Check for validation of the k-avoiding property after each addition.
- question_mark
The interviewer should be able to reason through the process of constructing the array and handling edge cases.
常见陷阱
外企场景- error
Not checking the sum of pairs during array construction.
- error
Failing to skip numbers that would create an invalid pair.
- error
Rushing through the greedy process and missing an optimal choice.
进阶变体
外企场景- arrow_right_alt
Consider a variation where k is larger or smaller to test scalability.
- arrow_right_alt
Test with different n values to explore the boundary conditions.
- arrow_right_alt
Explore the possibility of optimizing the space complexity or using different data structures.