移动互联网包含( )三个方面,seo网站优化工具大全,欧美品牌网站设计,成华区建设局门户网站Every day a Leetcode
题目来源#xff1a;2834. 找出美丽数组的最小和
解法1#xff1a;贪心
从最小正整数 1 开始枚举#xff0c;设当前数为 num#xff0c;如果 nums 里没有 target - num#xff0c;就说明可以添加 num#xff0c;依次填满直到有 n 个数即可。
用…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){setint 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 和 target-1 只能选其中一个为了使美丽数组的总和最小我们选1。2 和 target-2 只能选其中一个为了使美丽数组的总和最小我们选2。…一直到 ⌊target/2⌋无论 target 是奇数还是偶数它都可以选。
设 m min(n, ⌊target/2⌋)我们选择1~m总和为 m(m1)/2。
此时还剩下 n-m 个数只能从 target 开始往后选一直到 targetn-m-1。
代码
/** lc appleetcode.cn id2834 langcpp** [2834] 找出美丽数组的最小和*/// lc codestart
// class Solution
// {
// private:
// const int MOD 1e9 7;// public:
// int minimumPossibleSum(int n, int target)
// {
// setint 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 codeend结果 复杂度分析
时间复杂度O(1)。
空间复杂度O(1)。
