README.md

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

English Version

题目描述

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

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

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

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

解法

方法一：贪心 + 哈希表

我们从正整数 $i=1$ 开始，依次判断 $i$ 是否可以加入数组中，如果可以加入，则将 $i$ 加入数组中，累加到答案中，然后将 $target-i$ 置为已访问，表示 $target-i$ 不能加入数组中。循环直到数组长度为 $n$。

时间复杂度 $O(n+target)$，空间复杂度 $O(n+target)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        vis = set()
        ans = 0
        i = 1
        for _ in range(n):
            while i in vis:
                i += 1
            ans += i
            vis.add(target - i)
            i += 1
        return ans

Java

class Solution {
    public long minimumPossibleSum(int n, int target) {
        boolean[] vis = new boolean[n + target];
        long ans = 0;
        for (int i = 1; n > 0; --n, ++i) {
            while (vis[i]) {
                ++i;
            }
            ans += i;
            if (target >= i) {
                vis[target - i] = true;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        bool vis[n + target];
        memset(vis, false, sizeof(vis));
        long long ans = 0;
        for (int i = 1; n; ++i, --n) {
            while (vis[i]) {
                ++i;
            }
            ans += i;
            if (target >= i) {
                vis[target - i] = true;
            }
        }
        return ans;
    }
};

Go

func minimumPossibleSum(n int, target int) (ans int64) {
	vis := make([]bool, n+target)
	for i := 1; n > 0; i, n = i+1, n-1 {
		for vis[i] {
			i++
		}
		ans += int64(i)
		if target >= i {
			vis[target-i] = true
		}
	}
	return
}

TypeScript

function minimumPossibleSum(n: number, target: number): number {
    const vis: boolean[] = Array(n + target).fill(false);
    let ans = 0;
    for (let i = 1; n; ++i, --n) {
        while (vis[i]) {
            ++i;
        }
        ans += i;
        if (target >= i) {
            vis[target - i] = true;
        }
    }
    return ans;
}

...