[LeetCode] 每日一题 2829. k-avoiding 数组的最小总和（简单的数学推导）

题目链接

https://leetcode.cn/problems/determine-the-minimum-sum-of-a-k-avoiding-array

题目描述

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

提示

• m == grid.length

• n == grid[i].length

• 1 <= m, n, grid[i][j] <= 50

解题思路

这道题的核心在于构造一个 k-avoiding 数组，即保证数组中任意两个不同元素的和不等于 k，并让数组的总和尽可能小。题目要求长度为 n，因此我们需要在 最小化和 和 满足 k-avoiding 条件 之间找到平衡

数学推导

1. 分析 k-avoiding 条件

   • 在 1 ~ k-1 的范围内，所有满足 x + y = k 的数对都是 互斥的，即我们在每对 (x, k - x) 里最多只能选取一个数

   • 为了让总和最小，优先选择较小的数，即从 1 开始选，直到 k/2 为止

2. 确定可选的最小元素集合

   • 从 1 开始选，直到 min(n, k/2) 个数字。这部分的和可以通过等差数列求和公式计算

3. 如果选取数量不足 n

   • 选取 k/2 个数后，如果还不够 n 个元素，则需要从 k 开始继续添加额外的数字，直到总数达到 n

4. 使用等差数列求和

   • 由于所有选取的数是连续的，直接使用等差数列求和公式 (首项 + 末项) * 项数 / 2，可快速计算所需总和

代码实现

class Solution {
    public int minimumSum(int n, int k) {
        int num = Math.min(n, k / 2);
        int part1 = getSum(1, num, num);
        int part2 = getSum(k, k + n - num - 1, n - num);
        return part1 + part2;
    }

    private int getSum(int begin, int end, int n) {
        return (begin + end) * n / 2;
    }
}

复杂度分析

• 时间复杂度： O(1) 🚀

  • 代码只进行了简单的数学计算，没有循环，所有计算都是常数时间完成的，因此时间复杂度为 O(1)

• 空间复杂度： O(1) 🏎️

  • 只用了几个整数变量，没有额外的空间开销，所以空间复杂度也是 O(1)

总结

这道题的解法完全依赖于 数学推导，通过观察 k-avoiding 条件，我们找到了最优策略：优先选取 1 ~ k/2 之间的数，如果数量不足 n，则从 k 继续填充。借助等差数列求和公式，我们可以在 O(1) 的时间内快速计算最小总和。整体思路简洁高效，是一道很好的数学归纳题目✨

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。