找出美丽数组的最小和
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
nums.length == n.
nums 由两两互不相同的正整数组成。
在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。
返回符合条件的美丽数组所可能具备的 最小 和。
示例 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^5\)
\(1 <= target <= 10^5\)
解题思路1
见代码注释，直接构造整个数组。时间复杂度O(n)。
code1
class Solution {
public:
//美丽数组的定义：
//1.长度为n
//2.两两互不相同的正整数
//3.两两相加不等于target
//符合条件的最小和
//选1不能选target-1
//选2不能选target-2
//...
long long minimumPossibleSum(int n, int target) {
long long int ans = 0;
int cnt = 0,idx = 1;
set<int> choose;
while(cnt < n)
{
if(!choose.count(target-idx))
{
ans += idx;
choose.insert(idx);
cnt ++;
}
//for(auto item : choose) cout<<item<<" ";
//cout<<cnt<<endl;
idx++;
}
return ans;
}
};
解题思路2：数学
可以发现：
1和target-1选1；
2和target-2选2；
....
一直到\(\lfloor \frac{target}{2} \rfloor\),可以直接选择。
取m = min(\(\lfloor \frac{target}{2} \rfloor\),n),那么第一段的和为：
\[\frac{m(m+1)}{2}
\]
第二段还需要选择n - m个数，最小值为target,最大值为target+n-m-1,那么第二段的和为：
\[\frac{(2target + n - m - 1)(n-m)}{2}
\]
code2
class Solution {
public:
long long minimumPossibleSum(int n, int target) {
long long int m = min(target / 2,n);
return m * (m + 1) / 2 + (2 * target + n - m -1)*(n - m) / 2;
}
};