日期: 2025 年 3 月 26 日

目标

给你两个整数 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

思路

定义 k-avoiding 数组是由不同的正整数组成，并且任意两个元素的和不等于 k 的数组。求长度为 n 的 k-avoiding 数组的最小和。

构造一个长度为 n 的正整数数组，要使和最小，需要从 num = 1 开始选，跳过 k - num。

网友指出可以使用等差数列求和来计算，第一部分是 1 ~ m, m = min(k / 2, n) 和为 m * (m + 1) / 2，第二部分是 k ~ k + n - m - 1，和为 (n - m) * (2 * k + n - m - 1) / 2。

代码

/**
 * @date 2025-03-26 0:13
 */
public class MinimumSum2829 {

    public int minimumSum(int n, int k) {
        int res = 0;
        int length = 0;
        int num = 1;
        Set<Integer> avoiding = new HashSet<>();
        while (length < n) {
            if (avoiding.contains(num)) {
                num++;
                continue;
            }
            if (num < k) {
                avoiding.add(k - num);
            }
            length++;
            res += num;
            num++;
        }
        return res;
    }

}

性能