2829. k-avoiding 数组的最小总和(中等)

Posted on In Views:

1，问题描述

2829. k-avoiding 数组的最小总和

难度：中等

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

示例 1：

1
2
3
4
输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

1
2
3
4
输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。

提示：

  • 1 <= n, k <= 50

2，初步思考

​ 我自己最初使用的是set缓存遍历的方法，但是看到官方的数学方法感觉更好一些

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package days;

import java.util.HashSet;
import java.util.Set;

public class _2829k_avoiding数组的最小总和 {

    // 官方题解：数学推导
    public int minimumSum_gov(int n, int k) {
        if (n <= k / 2) {
            return arithmeticSeriesSum(1, 1, n);
        } else {
            return arithmeticSeriesSum(1, 1, k / 2) + arithmeticSeriesSum(k, 1, n - k / 2);
        }
    }

    private int arithmeticSeriesSum(int a1, int d, int n) {
        return (a1 + a1 + (n - 1) * d) * n / 2;
    }


    // 解法：数学逻辑推导
    // 时间复杂度：O(n)，空间复杂度：O(1)
    // 求解1～n的连续等差数列的和
    public int minimumSum_math(int n, int k) {
        int half = k / 2;// 例如：k=5。1，2，3，，，5，6，7，8，9
        if (n <= half) {
            return continuousMonotonicSummation(1, n);
        } else {
            return continuousMonotonicSummation(1, half) + continuousMonotonicSummation(k, k + n - half - 1);
        }
    }

    private int continuousMonotonicSummation(int start, int end) {
        return (end - start + 1) * (end + start) / 2;
    }

    // 解法：使用set存储已经使用的数字，然后每次都取最小的，如果取到k-idx，则不加入set中，直到set的size等于n，然后求和即可
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public int minimumSum_set(int n, int k) {
        Set<Integer> set = new HashSet<>();
        int idx = 1;
        while (set.size() < n) {
            if (!set.contains(k - idx)) {
                set.add(idx);
            }
            idx++;
        }
        int res = 0;
        for (Integer i : set) {
            res += i;
        }
        return res;
    }

    public static void main(String[] args) {
        _2829k_avoiding数组的最小总和 avoiding = new _2829k_avoiding数组的最小总和();
        System.out.println(avoiding.minimumSum_math(5, 4));//18
        System.out.println(avoiding.minimumSum_math(2, 6));//3
        System.out.println(avoiding.minimumSum_math(2, 1));//3
    }

}

/**
 * n=5,k=4
 * n=2,k=1
 * mid=1,
 */