Medium

题目描述

给你正整数 n 和 target。

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

  • nums.length == n
  • nums 由两两不同的正整数组成
  • 不存在两个不同的下标 i 和 j，使得 nums[i] + nums[j] == target

返回美丽数组可能的最小和，答案对 10^9 + 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^9
  • 1 <= target <= 10^9

解题思路

这道题需要构造一个长度为n的数组，使得数组中任意两个数的和都不等于target，并且数组和最小。

核心思路：贪心选择

为了使数组和最小，我们贪心地从最小的正整数1开始选择。对于每个数x，如果它与之前选择的某个数的和等于target，那么就不能选择x。

关键观察：

  1. 如果选择了数字x，那么就不能选择(target - x)
  2. 从1开始贪心选择，当遇到某个数x时，如果(target - x)还没有被选择，那么我们优先选择较小的x
  3. 可以将可选数字分为两部分：[1, target/2] 和 [target, +∞)

具体分析：

  • 对于小于target/2的数字，每选择一个数x，就排除了(target - x)
  • 当选择完[1, target/2)范围内的数字后，如果还需要更多数字，就从target开始继续选择

算法步骤：

  1. 计算可以从[1, target/2]范围选择多少个数字，记为k
  2. 如果k >= n，直接返回前n个数的和
  3. 否则选择[1, target/2]的所有数字，再从target开始选择剩余的数字

时间复杂度可以优化到O(1)，使用数学公式计算等差数列和。

代码实现

class Solution {
public:
    int minimumPossibleSum(int n, int target) {
        const int MOD = 1e9 + 7;
        long long half = target / 2;
        
        if (n <= half) {
            // 选择 [1, n]
            return (long long)n * (n + 1) / 2 % MOD;
        } else {
            // 选择 [1, half] 和 [target, target + (n - half) - 1]
            long long sum1 = half * (half + 1) / 2 % MOD;
            long long remaining = n - half;
            long long sum2 = (2LL * target + remaining - 1) * remaining / 2 % MOD;
            return (sum1 + sum2) % MOD;
        }
    }
};

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        MOD = 10**9 + 7
        half = target // 2
        
        if n <= half:
            # 选择 [1, n]
            return n * (n + 1) // 2 % MOD
        else:
            # 选择 [1, half] 和 [target, target + (n - half) - 1]
            sum1 = half * (half + 1) // 2 % MOD
            remaining = n - half
            sum2 = (2 * target + remaining - 1) * remaining // 2 % MOD
            return (sum1 + sum2) % MOD

public class Solution {
    public int MinimumPossibleSum(int n, int target) {
        const int MOD = 1000000007;
        long half = target / 2;
        
        if (n <= half) {
            // 选择 [1, n]
            return (int)((long)n * (n + 1) / 2 % MOD);
        } else {
            // 选择 [1, half] 和 [target, target + (n - half) - 1]
            long sum1 = half * (half + 1) / 2 % MOD;
            long remaining = n - half;
            long sum2 = (2L * target + remaining - 1) * remaining / 2 % MOD;
            return (int)((sum1 + sum2) % MOD);
        }
    }
}

/**
 * @param {number} n
 * @param {number} target
 * @return {number}
 */
var minimumPossibleSum = function(n, target) {
    const MOD = 1e9 + 7;
    const half = Math.floor(target / 2);
    
    if (n <= half) {
        // 选择 [1, n]
        return Math.floor(n * (n + 1) / 2) % MOD;
    } else {
        // 选择 [1, half] 和 [target, target + (n - half) - 1]
        const sum1 = Math.floor(half * (half + 1) / 2) % MOD;
        const remaining = n - half;
        const sum2 = Math.floor((2 * target + remaining - 1) * remaining / 2) % MOD;
        return (sum1 + sum2) % MOD;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(1)
空间复杂度O(1)