目标
给你两个正整数：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
思路
首先，美丽数组一个长度为n的数组，数组中的元素均不相同且为正整数，且任意两个元素之后不能等于target。
我们需要寻找所有可能的美丽数组中，所有元素和最小的那一个。并返回这个最小和。
如何才能使元素和最小？
很明显应该是从1开始的正整数序列，但是这个序列中的值相加不能等于target。
那么本质上是要求 1______mid~~~~~~target______这一序列的值，其中~~~~~~区间的值应舍去，因为会与前面的相加得到target。
刚开始想的是循环遍历 [1, n) 累加和，并记录target - i，如果遍历的过程中遇到了就直接跳过，但是提交后提示超出内存限制。于是进行修改，不保存不符合条件的元素，直接根据下标来判断，这次提示超时。
然后尝试不使用循环，直接使用等差数列求和公式计算，结果整型溢出。需要注意运算符优先级高的会先计算，如果没有显式地类型转换就会溢出，并且隐式类型转化使用的是溢出后的值。
代码
/**
* @date 2024-03-08 9:00
*/
public class MinimumPossibleSum {
public final int MOD = 1000000007;
public int minimumPossibleSum(int n, int target) {
int mid;
mid = target / 2;
if (n <= mid) {
return (int) ((n + n * (n - 1L) / 2L) % MOD);
} else {
int r = n - mid;
return (int) (((mid + mid * (mid - 1L) / 2L) + (long) target * r + r * (r - 1L) / 2L) % MOD);
}
}
}
性能
