难度: Medium
给你两个整数 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运行时间: 23 ms
内存: 16.1 MB
class Solution:
def minimumSum(self, n: int, k: int) -> int:
mid = k // 2
if n <= mid:
return (1 + n) * n // 2
return (1 + mid) * mid // 2 + (k + (k + n - mid - 1)) * (n - mid) // 2
要构造一个长度为 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
考虑 `mid` 即 `k/2` 的整数部分是关键，因为任何两个小于或等于 `mid` 的正整数相加都不会等于 `k`。这是因为最大可能的和是 `mid + mid`，这等于 `k`（当 `k` 为偶数时）或小于 `k`（当 `k` 为奇数时）。因此，只要我们使用的数字都小于或等于 `mid`，就可以保证没有任何两个数字的和等于 `k`。这个逻辑帮助我们构造出前半部分的数组，确保不会违反 k-avoiding 的条件。
当 `n` 超过 `mid` 时，从 `k` 开始取数而不是更大的数，是为了确保数组的剩余部分与前半部分中的任何数相加都不会产生和为 `k` 的情况。从 `k` 开始取数可以最大化地利用数字范围，同时避免与前半部分 `[1, 2, ..., mid]` 中的数相加得到 `k`。如果从比 `k` 更大的数开始，可能会导致数字范围不够用，或者不必要地增加数组元素的总和。
这个公式是等差数列求和的标准公式。在这里，我们从 `k` 开始，到 `k + (n - mid - 1)` 结束，共有 `n - mid` 个数。这个序列的首项是 `k`，末项是 `k + (n - mid - 1)`，因此其和可以通过求等差数列和的公式计算：`(首项 + 末项) * 项数 / 2`。这种方法确保了计算的准确性和效率，同时满足了题目要求避免和为 `k` 的情况。
此方法在大多数情况下有效，但当 `k` 非常接近 `n` 时，特别是 `k` 小于或等于 `n` 时，可能会遇到问题。例如，如果 `k` 等于 `n`，那么从 `1` 到 `n` 的数每两个数相加都可能得到 `k`。在这种极端情况下，我们可能需要考虑不同的策略或确认给定的 `k` 和 `n` 是否适用于此方法。如果 `k` 非常小，可能不存在完全避免和为 `k` 的构造方法，因为可用的数字范围有限。