2834-找出美丽数组的最小和

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

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

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

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 109 + 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 <= 109
• 1 <= target <= 109

请看 视频讲解 第二题。

把 target 记作 k。

对于 [1,k-1] 内的数字：

• 1 和 k-1 只能选其中一个；
• 2 和 k-2 只能选其中一个；
• 3 和 k-3 只能选其中一个；
• ……
• 一直到 \left\lfloor\dfrac{k}{2}\right\rfloor，无论 k 是奇数还是偶数，它都可以选。

设 m=\min\left(\left\lfloor\dfrac{k}{2}\right\rfloor, n\right)，那么答案的第一段是从 1 到 m，元素和为

\dfrac{m(m+1)}{2}

此时还剩下 n-m 个数，只能从 k 开始往后选，那么答案的第二段是从 k 到 k+n-m-1，元素和为

\dfrac{(2k+n-m-1)(n-m)}{2}

所以答案为

\dfrac{m(m+1) + (2k+n-m-1)(n-m)}{2}

[sol-Python3]

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 % (10 ** 9 + 7)

[sol-Java]

class Solution {
    public int minimumPossibleSum(int n, int k) {
        long m = Math.min(k / 2, n);
        return (int) ((m * (m + 1) + (n - m - 1 + k * 2) * (n - m)) / 2 % 1000000007);
    }
}

[sol-C++]

class Solution {
public:
    int minimumPossibleSum(int n, int k) {
        long long m = min(k / 2, n);
        return (m * (m + 1) + (n - m - 1 + k * 2) * (n - m)) / 2 % 1000000007;
    }
};

[sol-Go]

func minimumPossibleSum(n, k int) int {
	m := min(k/2, n)
	return (m*(m+1) + (k*2+n-m-1)*(n-m)) / 2 % 1_000_000_007
}

func min(a, b int) int { if b < a { return b }; return a }

[sol-JavaScript]

var minimumPossibleSum = function (n, k) {
    const m = Math.min(k >> 1, n);
    const res = BigInt(m) * BigInt(m + 1) + BigInt(k * 2 + n - m - 1) * BigInt(n - m)
    return Number((res / BigInt(2)) % BigInt(1000000007));
};

复杂度分析

• 时间复杂度：\mathcal{O}(1)。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。