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

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

题目描述

给定两个正整数 n 和 target，目标是找到一个长度为 n 的数组，满足以下条件：

数组由两两不同的正整数组成。
不存在两个不同下标 i 和 j 使得 nums[i] + nums[j] == target。
返回符合条件的美丽数组所可能具备的最小和，并对结果进行 10^9 + 7 取模。

测试用例

示例 1：

输入：n = 2, target = 3
输出：4

示例 2：

输入：n = 3, target = 3
输出：8

示例 3：

输入：n = 1, target = 1
输出：1

原始思路

方案

初始方案是从最小的数字开始，逐个检查每个数字是否可以被添加到数组中，同时确保不会存在两个数字之和等于 target。

从 1 开始逐个尝试添加数字到数组。
对于每个数字，检查是否与数组中已有的数字相加会得到 target。
如果不会，将其添加到数组中。
继续此过程，直到数组长度达到 n。

代码

def minimumPossibleSum(n, target):
    selected_nums = set([1])
    total_sum = 1
    current_num = 2

    while len(selected_nums) < n:
        if all((current_num + num != target) for num in selected_nums):
            selected_nums.add(current_num)
            total_sum += current_num
        current_num += 1

    return total_sum % (10**9 + 7)

复杂度分析

时间复杂度：O(n^2)，因为每个数字的添加都需要遍历已选择的数字集合。
空间复杂度：O(n)，用于存储选择的数字集合。

贪心优化

方案

优化策略：
- 避免集合的使用：
  - 引入“避免”集合，存储所有与已选数字相加得到 target 的数字。
  - 这样可以快速检查新数字是否会导致和为 target 的情况。
- 直接检查：
  - 每次选择一个新数字时，仅检查它是否在“避免”集合中。
  - 不在集合中的数字被认为是安全的，可以直接添加。
- 动态更新避免集合：
  - 当新数字被添加到美丽数组时，相应的 target - 新数字 也被添加到“避免”集合中。
  - 这确保任何可能与新数字组成 target 的数字在未来都会被避免。
优化后的时间复杂度：
- 每个数字只需进行一次集合检查。
- 时间复杂度降低为 O(n)，显著提高了算法效率。

代码

def minimumPossibleSum_optimized(n, target):
    selected_nums = set()
    avoid_nums = set()
    total_sum = 0
    current_num = 1

    while len(selected_nums) < n:
        if current_num not in avoid_nums:
            selected_nums.add(current_num)
            total_sum += current_num
            avoid_nums.add(target - current_num)
        current_num += 1

    return total_sum % (10**9 + 7)

复杂度分析

时间复杂度：O(n)，因为每个数字只需检查一次。
空间复杂度：O(n)，用于存储选择的数字和避免数字集合。

数学方法

方案

针对上述问题，我们采用了一种更高效的数学方法来解决这个问题。该方法通过分析问题的数学本质，减少了必要的计算量，特别适用于处理大规模数据。

问题分解：
- 首先，我们将问题分解为两部分。由于数组中的数字都是唯一的，且两个不同的数字之和不能等于 target，我们首先从最小的数字开始选择，直到我们不能再选择更多的数字而不违反和的规则。
选择前半部分的数字：
- 在 1 到 target-1 的范围内，某些数字不能同时出现。例如，如果 target 是 6，则 1 和 5、2 和 4 不能同时出现，因为它们的和等于 6。但是，3（当 target 是偶数）或 3 和 2（当 target 是奇数）是可以被选择的。
- 这意味着我们可以自由选择从 1 到 m 的数字，其中 m = min(⌊target/2⌋, n)。对于这部分数字，我们可以直接使用等差数列的求和公式来计算它们的总和，即 m * (m + 1) / 2。
选择后半部分的数字：
- 一旦我们选择了前 m 个数字，剩下需要选择的数字的数量就是 n - m。由于我们已经选择了 1 到 m，我们现在需要从 target 开始选择剩下的数字。
- 如果 n 大于 m，那么我们将从 target 开始连续选择 n - m 个数字。这些数字的总和可以用等差数列的求和公式来计算，公式为：(2 * target + n - m - 1) * (n - m) / 2。
计算总和并取模：
- 我们将两部分的和相加，并对结果进行 10^9 + 7 取模，以得到最终答案。

实现

第一部分和：从 1 到 min(target // 2, n) 的和。
第二部分和（如果需要）：从 target 开始，选择的 n - min(target // 2, n) 个数字的和。
将这两部分的和相加，即得到符合条件的美丽数组的最小和。

选择小于 target // 2 的数字：
- 当我们从 1 开始逐渐增加数字，直到 target // 2，这些数字不可能与数组中的其他数字相加得到 target。
- 例如，如果 target 是 10，那么 target // 2 是 5。在这种情况下，1 到 5 之间的任何两个数字相加都不会等于 10。
- 因此，这部分的选择是安全的，并且由于我们需要最小和，所以我们从 1 开始逐一增加。
**当 n 大于 target // 2**：
- 如果 n 大于 target // 2，这意味着仅仅选择小于 target // 2 的数字不足以填满数组。
- 在这种情况下，我们需要继续选择更多的数字，但为了避免和为 target 的组合，我们需要从 target 本身开始选择。
- 我们继续逐一增加，直到数组长度达到 n。
计算总和：
- 第一部分是从 1 到 min(target // 2, n) 的和。
- 第二部分（如果需要）是从 target 开始，选择剩下的 n - min(target // 2, n) 个数字。
- 最后，将这两部分的和加起来，就是我们要找的最小和。

这是一个通过数学方法来解决问题的典型例子，它避免了复杂的编程逻辑，提供了一种更简洁高效的解决方案。

代码

def minimumPossibleSum_math_approach(n, target):
    MOD = 10**9 + 7
    m = min(target // 2, n)
    first_half_sum = m * (m + 1) // 2
    remaining = n - m
    second_half_sum = (2 * target + remaining - 1) * remaining // 2
    return (first_half_sum + second_half_sum) % MOD

复杂度分析

时间复杂度：O(1)，因为结果是通过直接计算得出的。
空间复杂度：O(1)，只使用了固定数量的变量。