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

题目描述：

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

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

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

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

---

解题分析及思路：

方法一：哈希表

思路：

为使得数组的和最小，我们可以从1开始，依次找到满足条件的数，直到找到n个数为止。

而条件为：在已经添加过的数中，不存在一个数，使得两个数的和等于target，即target-x不在已经添加的数中。

那么就变成如何判断target-x是否在已经添加的数中，这里可以使用哈希表来存储已经添加的数。

func minimumPossibleSum(n int, target int) int {
	const mod = 1e9 + 7
	m := make(map[int]bool)
	count := 0
	x := 1
	for count < n {
		if !m[target-x] {
			m[x] = true
			count++
		}
		x++
	}
	var sum int
	for key := range m {
		sum += key
	}
	return sum % mod
}

可惜的是，这种方法在n很大的时候，会超时。

复杂度：

• 时间复杂度：O(N)，其中 N 是x的大小。
• 空间复杂度：O(N)，只使用常数额外空间。

方法二：数学

思路：

由于方法一超时，我们需要寻找更优的方法。

那么是否可以通过数学的方法来解决呢？

我们可以发现：

• 当从1开始添加数时，直到添加到target/2为止，而(target/2, target)之间的数，不能添加，因为这些数与[1, target/2]之间的数相加，必定会等于target。
• 若添加到target/2后，所有个数仍小于n时，就要从target 开始添加，直到添加到n个数为止。

那么此时就是求[1, target/2]之间的数的和，以及[target, target+n-target/2]之间的数的和。

令m=target/2所以能够得到如下的公式：

sum = (1+2+...+target/2) + (target + target+1 + ... + (target+n-target/2))
=> sum = m*(m+1)/2 + (target+target+n-m)*(target+n-m)/2 - (target-1)*(target)/2
=> sum = (m*(m+1) + (target+n-m-1)*(target+n-m) - (target-1)*(target))/2
=> sum = (m*m + m + target*n - target*m - n*m + (n*n-n)/2)

最后对结果取模即可，其中存在两种情况：

• 当n<=m时，直接返回(1+2+…+n)的和。
• 当n>m时，返回上述公式的结果。

func minimumPossibleSum2(n int, target int) int {
	const mod int = 1e9 + 7
	m := target / 2
	if n <= m {
		return ((1 + n) * n / 2) % mod
	}
	return (m*m + m + target*n - target*m - n*m + (n*n-n)/2) % mod
}

复杂度：

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

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用
• 内存消耗:2 MB,击败了18.18% 的Go用户