找出美丽数组的最小和

You are given positive integers n and target.

An array nums is beautiful if it meets the following conditions:

• nums.length == n.
• nums consists of pairwise distinct positive integers.
• There doesn't exist two distinct indices, i and j, in the range [0, n - 1], such that nums[i] + nums[j] == target.

Return the minimum possible sum that a beautiful array could have modulo 109 + 7.

 

Example 1:

Input: n = 2, target = 3
Output: 4
Explanation: We can see that nums = [1,3] is beautiful.
- The array nums has length n = 2.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 4 is the minimum possible sum that a beautiful array could have.

Example 2:

Input: n = 3, target = 3
Output: 8
Explanation: We can see that nums = [1,3,4] is beautiful.
- The array nums has length n = 3.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 8 is the minimum possible sum that a beautiful array could have.

Example 3:

Input: n = 1, target = 1
Output: 1
Explanation: We can see, that nums = [1] is beautiful.

 

Constraints:

• 1 <= n <= 109
• 1 <= target <= 109

/*
思路：
1. 为了避免 nums[i] + nums[j] == target，我们需要选择 nums 中的元素，使得没有两个数之和等于 target。
2. 使用 Java Stream 来生成和处理数组。
3. 最小的 n 个正整数的和是 1 + 2 + ... + n = n * (n + 1) / 2。
4. 遍历数组，若出现 nums[i] + nums[j] == target，则替换 nums[j] 为 nums[j] + 1。
5. 取模 10^9 + 7 返回最终结果。
*/

import java.util.stream.IntStream;

public class BeautifulArrayStream {
    public int beautifulArray(int n, int target) {
        int mod = 1000000007;
        long sum = IntStream.rangeClosed(1, n).sum();
        int i = 1;
        while (i <= n && sum % target == 0) {
            sum = (sum - i + (i + 1)) % mod;
            i++;
        }
        return (int) (sum % mod);
    }
}

此题解的核心思路是通过数学方法计算出美丽数组的最小和。首先，它通过计算m=min(k//2,n)，确定数组中最小值部分的数目m。这是因为在数组中任意两个数之和不能等于给定的目标值k，因此选择数值尽可能小的m个数可以确保它们的和小于k。接着题解利用了算术级数求和的公式来计算前m个自然数的和以及剩余部分的和，通过这种方式可以快速得到整个数组的和。最后，为了处理可能的大数字，结果对1_000_000_007取模来满足题目要求。

O(1)

O(1)