How do I handle the large values of n and target in this problem?

Use a greedy approach to iteratively select valid numbers while ensuring distinctness and avoiding sums that match the target. The sum should be calculated modulo 10^9 + 7.

What is the greedy approach in this problem?

The greedy approach selects the smallest number that satisfies the problem's constraints and avoids sums matching the target, progressively building the array.

What does it mean to validate the invariant in this problem?

Validating the invariant means ensuring no two distinct numbers in the array sum up to the target at every step of the greedy selection.

What is the final step after constructing the array?

The final step is to calculate the sum of the array modulo 10^9 + 7 to ensure the result fits within the specified range.

How can I optimize my solution for larger values of n?

You can optimize by carefully selecting numbers and ensuring the greedy approach minimizes computational complexity while maintaining the invariant.

#2834

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

找出美丽数组的最小和

给你两个正整数： n 和 target 。如果数组 nums 满足下述条件，则称其为美丽数组。 nums.length == n . nums 由两两互不相同的正整数组成。在范围 [0, n-1] 内，不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == …

数学贪心

题目描述

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

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

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

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

lightbulb

解题思路

方法一：贪心 + 数学

我们可以贪心地从 $x = 1$ 开始构造数组 $nums$ ，每次选择 $x$ ，并且排除 $target - x$ 。

我们不妨记 $m = \left\lfloor \frac{target}{2} \right\rfloor$ 。

如果 $x <= m$ ，那么我们可以选择的数有 $1, 2, \cdots, n$ ，所以数组的和为 $\left\lfloor \frac{(1+n)n}{2} \right\rfloor$ 。

如果 $x > m$ ，那么我们可以选择的数有 $1, 2, \cdots, m$ ，共 $m$ 个数，以及 $n - m$ 个从 $target$ 开始的数，所以数组的和为 $\left\lfloor \frac{(1+m)m}{2} \right\rfloor + \left\lfloor \frac{(target + target + n - m - 1)(n-m)}{2} \right\rfloor$ 。

注意，我们需要对结果取模 $10^9 + 7$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        mod = 10**9 + 7
        m = target // 2
        if n <= m:
            return ((1 + n) * n // 2) % mod
        return ((1 + m) * m // 2 + (target + target + n - m - 1) * (n - m) // 2) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of greedy algorithms.
question_mark
The candidate applies the concept of invariant validation correctly.
question_mark
The candidate is mindful of the problem's constraints and uses the modulo operation effectively.

warning

常见陷阱

外企场景

error
Selecting numbers that violate the sum condition.
error
Failing to ensure all integers are distinct.
error
Incorrectly handling large values of n and target within the constraints.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we allow non-distinct integers in the array?
arrow_right_alt
How would the approach change if n was significantly larger?
arrow_right_alt
What if we needed to minimize the product instead of the sum?

help

常见问题

外企场景

继续练习

#2829 k-avoiding 数组的最小总和 #2842 统计一个字符串的 k 子序列美丽值最大的数目 #2844 生成特殊数字的最少操作