找出美丽数组的最小和

难度: Medium

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

nums.length == n.
nums 由两两互不相同的正整数组成。
在范围 [0, n-1] 内，不存在 两个不同下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的最小和，并对结果进行取模 10⁹ + 7。

示例 1：

输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。

示例 2：

输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。 
- nums 的长度为 n = 3 。 
- nums 由两两互不相同的正整数组成。 
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。

示例 3：

输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。

提示：

1 <= n <= 10⁹
1 <= target <= 10⁹

Submission

运行时间: 16 ms

内存: 16.1 MB

class Solution:
    def minimumPossibleSum(self, n: int, k: int) -> int:
        m = min(k // 2, n)
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2 % 1_000_000_007

Explain

此题解的核心思路是通过数学方法计算出美丽数组的最小和。首先，它通过计算m=min(k//2,n)，确定数组中最小值部分的数目m。这是因为在数组中任意两个数之和不能等于给定的目标值k，因此选择数值尽可能小的m个数可以确保它们的和小于k。接着题解利用了算术级数求和的公式来计算前m个自然数的和以及剩余部分的和，通过这种方式可以快速得到整个数组的和。最后，为了处理可能的大数字，结果对1_000_000_007取模来满足题目要求。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def minimumPossibleSum(self, n: int, k: int) -> int:
        # 计算m为目标k的一半与n的较小值，防止数组中两数之和等于k
        m = min(k // 2, n)
        # 计算前m个数的和，以及m到n-1的数的和，使用等差数列求和公式
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2 % 1_000_000_007

Explore

选择m=min(k//2, n)是为了保证在数值范围内尽可能地避免任意两个数的和等于target。当我们取数值从1开始到m时，最大可能的和是m*(m+1)/2，这一和小于k，因为m最大为k//2。这样做可以确保在选择的这些数中，不会有任何两个数的和达到或超过target，这是因为最大的两个数之和也仅为2*m，而2*m最大是k，但不包括k。因此，这种选择有效避免了和为target的情况。

在解题中使用等差数列求和公式是因为这可以快速计算连续数列的和。前m个自然数是一个简单的等差数列，其和可以直接使用公式m*(m+1)/2来计算，这样的计算非常高效。对于m到n-1的数，我们可以假设这些数是接续的最小的数，确保和最小，同样形成一个等差数列。使用等差数列的求和公式可以快速计算出这部分的和，提高了效率。整体来说，这种数列的选择和分布有助于快速且准确地计算出整个数组的和，从而寻找到满足条件的最小和。

题解中通过计算m=min(k//2, n)来选择数值，确保选取的每个数从1到m，这些数是最小的m个正整数。由于m是k的一半，所以任意两个这样的数相加，其和最大为2*m，这小于k。这样就保证了这些数两两相加不会等于target。对于m之后到n-1的数，题解选择继续使用大于m的最小整数，即从m+1开始，以此类推，这些数加起来的和同样不会恰好等于target，因为它们的起始点已经大于m，和会超过k。