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

难度: 中等

来源: 第 360 场周赛 第二题

---

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

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

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

返回符合条件的美丽数组所可能具备的 最小 和。

示例 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 <= 105
• 1 <= target <= 105

class Solution {
    public long minimumPossibleSum(int n, int target) {

    }
}

分析与题解

---

• 贪心算法

  这个题目我们想要最小和的数组, 并且两两元素之和不能为 target.

  那么我们就先筛选从 [1 , target] 符合条件的元素.

  1 与 target-1 : 选择 1

  2 与 target-2 : 选择 2

  3 与 target-3 : 选择 3

  ...

  target/2 : 选择 target/2, 因为我们不可能搞两个 target/2 进入数组.

  这样, 在 [1 , target] 区间中符合的个数最大为 target/2 个.

  如果这时候, target/2 的个数满足 n 的要求, 也就是 target/2 >= n, 我们直接取个数为 n 即可.

  如果这时候, target/2 的个数不满足 n 的要求, 那么剩下的元素要从哪里取呢? 这需要从 [target, ∞] 中取剩下的个数, 这样才能满足 num[i] + num[j] != target 的条件.

  所以这时候, 在 [1 , target] 的取值和如下所示.

  long m = Math.min(n, targer/2);
  long fisrtSum = m * (m + 1) / 2;
  

  如果,个数还不够,那么就需要从 [target, ∞] 区间继续取值. 我们可以计算剩余的区间值.

  long secondSum = (n - m) * (target + (target + n - m - 1))/2;
  

  整体的解题思路如下所示.

  class Solution {
      public long minimumPossibleSum(int n, int target) {
          long m = Math.min(n, targer/2);
          long fisrtSum = m * (m + 1) / 2;
          long secondSum = (n - m) * (target + (target + n - m - 1))/2;
          return fisrtSum + secondSum;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(1)
  • 空间复杂度: O(1)

  结果如下所示.