要构造一个长度为 n 的 k-avoiding 数组,我们需要避免任何两个元素之和恰好为 k。解决方案的关键在于理解两个数相加等于 k 的可能性。\n\n首先,计算 k/2 的整数部分,记为 mid。这个值是能够与另一个数相加可能等于 k 的最大值。\n\n1. 如果 n 小于等于 mid,那么我们可以直接取最小的 n 个正整数,即 [1, 2, ..., n],因为在这个范围内任何两数之和都不会等于 k。\n\n2. 如果 n 大于 mid,我们需要考虑如何安排超出 mid 的那些数。首先我们取 [1, 2, ..., mid],然后从 k 开始取数,避免与前面的数相加等于 k。具体来说,从 k 取到 k + (n - mid - 1),确保不会有和为 k 的组合。\n\n因此,数组的构造分为两部分:前半部分直接取最小的 mid 个数,后半部分从 k 开始取,避免和前半部分的数相加得到 k。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def minimumSum(self, n: int, k: int) -> int:
mid = k // 2 # 计算 k/2 的整数部分
# 如果 n 小于等于 mid,直接返回前 n 个自然数的和
if n <= mid:
return (1 + n) * n // 2
# 如果 n 大于 mid,分成两部分计算:
# 1. 前 mid 个自然数的和
# 2. 从 k 到 k + (n - mid - 1) 的数的和
return (1 + mid) * mid // 2 + (k + (k + n - mid - 1)) * (n - mid) // 2