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

Every day a Leetcode

题目来源：2834. 找出美丽数组的最小和

解法1：贪心

从最小正整数 1 开始枚举，设当前数为 num，如果 nums 里没有 target - num，就说明可以添加 num，依次填满直到有 n 个数即可。

用集合 nums 存储数据保证唯一性。

代码：

class Solution
{
private:const int MOD = 1e9 + 7;public:int minimumPossibleSum(int n, int target){set<int> nums;nums.insert(1);int num = 2;while (nums.size() < n){if (!nums.count(target - num))nums.insert(num);num++;}return accumulate(nums.begin(), nums.end(), 0LL) % MOD;}
};

结果：

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

解法2：数学

我们发现了规律，对于 [1, target−1] 内的数字：

1. 1 和 target-1 只能选其中一个，为了使美丽数组的总和最小，我们选1。
2. 2 和 target-2 只能选其中一个，为了使美丽数组的总和最小，我们选2。
3. …
4. 一直到 ⌊target/2⌋，无论 target 是奇数还是偶数，它都可以选。

设 m = min(n, ⌊target/2⌋)，我们选择1~m，总和为 m(m+1)/2。

此时还剩下 n-m 个数，只能从 target 开始往后选，一直到 target+n-m-1。

代码：

/** @lc app=leetcode.cn id=2834 lang=cpp** [2834] 找出美丽数组的最小和*/// @lc code=start
// class Solution
// {
// private:
//     const int MOD = 1e9 + 7;// public:
//     int minimumPossibleSum(int n, int target)
//     {
//         set<int> nums;
//         nums.insert(1);
//         int num = 2;
//         while (nums.size() < n)
//         {
//             if (!nums.count(target - num))
//                 nums.insert(num);
//             num++;
//         }
//         return accumulate(nums.begin(), nums.end(), 0LL) % MOD;
//     }
// };class Solution
{
private:const int MOD = 1e9 + 7;public:int minimumPossibleSum(int n, int target){long long m = min(target / 2, n);return (cal(1, m) + cal(target, target + n - m - 1)) % MOD;}// 辅函数 - 返回 [left, right] 区间内元素和long long cal(int left, int right){long long sum = 0;for (int i = left; i <= right; i++)sum += i;return sum;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(1)。

空间复杂度：O(1)。