k-avoiding 数组的最小总和

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

 

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

 

Constraints:

• 1 <= n, k <= 50

// 思路：与普通Java版本类似，我们使用流来生成满足条件的数组。我们从1开始遍历，每次检查当前数字是否可以加入数组，如果满足条件则将其加入，最终求和返回。我们将遍历过程用Stream API来实现。

import java.util.stream.IntStream;

public class Solution {
    public int minimalSum(int n, int k) {
        return IntStream.iterate(1, i -> i + 1) // 从1开始的无限流
                .filter(current -> IntStream.range(1, current / 2 + 1) // 过滤掉那些不能加入的数字
                        .allMatch(i -> current - i != k - i))
                .limit(n) // 限制流的大小为n
                .sum(); // 求和
    }
}

要构造一个长度为 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)