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

【LetMeFly】2834.找出美丽数组的最小和：数学（等差数列求和）——O(1)的做法

力扣题目链接：https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/

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

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

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

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

方法一：数学（等差数列求和）——O(1)的做法

$n$个不同的正整数，任意两数之和不为$target$，问这些数的最小和为多少。

怎么构造这个数组？当然是每个元素越小越好。那就从$0,1,2,\cdots$开始呗。

这样最多能到几？最多能到$\lfloor\frac{target}2\rfloor$。

原理（可跳过）

在$\le target$的数当中，存在$a$则不能存在$target-a$。

例如$target=5$时，$1$和$4$不能同时存在。选哪个？もちろん选$4$。

如果这些数不够$n$个咋办？那就从$target$开始依次往上选就好了。$target, target + 1, target + 2, \cdots$，直到选够为止。

又有等差数列$a, a + 1, a + 2, \cdots, b$的和为$\frac{(a + b)\times(b - a + 1)}2$，因此可以在$O(1)$的时空复杂度内得出结果。

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N\log N)$

AC代码

C++

const int MOD = 1e9 + 7;
class Solution {  // AC,14.77%,62.50%
private:
    inline long long cal(long long l, long long r) {
        return (l + r) * (r - l + 1) / 2;
    }
public:
    int minimumPossibleSum(int n, int target) {
        long long half = target / 2;
        if (n <= half) {
            return cal(1, n);
        }
        return (cal(1, half) + cal(target, target + n - half - 1)) % MOD;
    }
};

Python

MOD = int(1e9) + 7
class Solution:
    def cal(self, l: int, r: int) -> int:
        return (l + r) * (r - l + 1) // 2

    def minimumPossibleSum(self, n: int, target: int) -> int:
        half = target >> 1
        if n <= half:
            return self.cal(1, n)
        return (self.cal(1, half) + self.cal(target, target + n - half - 1)) % MOD

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136565723