Medium

题目描述

给你两个整数 n 和 k。

如果一个由不同正整数组成的数组中不存在任何两个不同元素的和等于 k，则称该数组为 k-避免数组。

返回长度为 n 的 k-避免数组的最小可能和。

示例 1：

输入：n = 5, k = 4
输出：18
解释：考虑 k-避免数组 [1,2,4,5,6]，其和为 18。
可以证明不存在和小于 18 的 k-避免数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：我们可以构造数组 [1,2]，其和为 3。
可以证明不存在和小于 3 的 k-避免数组。

约束条件：

  • 1 <= n, k <= 50

提示：

  • 尝试从最小的可能整数开始
  • 检查当前数字是否可以添加到数组中
  • 要检查当前数字是否可以添加，请在集合中跟踪已添加的数字
  • 如果数字 i 被添加到数组中，那么 i + k 就不能被添加

解题思路

解题思路

这是一道贪心算法题目。核心思想是从最小的正整数开始，依次尝试添加到数组中，确保任意两个元素的和都不等于 k。

贪心策略：

  1. 从 1 开始遍历所有正整数
  2. 对于每个数字 i，检查是否可以添加到当前数组中
  3. 添加条件：i 不在已选择的数字集合中，且 k-i 也不在已选择的数字集合中
  4. 如果可以添加，就将 i 加入结果数组和集合中
  5. 重复直到数组长度达到 n

关键观察：

  • 如果选择了数字 i，那么数字 k-i 就不能选择（因为 i + (k-i) = k）
  • 贪心选择最小的数字能保证总和最小
  • 使用哈希集合来快速检查数字是否已被选择

这种方法保证了我们选择的数字组合是字典序最小的，从而使总和最小。

时间复杂度分析：

  • 最坏情况下需要遍历到 n + k/2 左右的数字
  • 每次检查和插入操作都是 O(1)
  • 总体时间复杂度为 O(n + k)

代码实现

class Solution {
public:
    int minimumSum(int n, int k) {
        unordered_set<int> used;
        int sum = 0;
        int current = 1;
        
        while (used.size() < n) {
            if (used.find(current) == used.end() && used.find(k - current) == used.end()) {
                used.insert(current);
                sum += current;
            }
            current++;
        }
        
        return sum;
    }
};

class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        used = set()
        total = 0
        current = 1
        
        while len(used) < n:
            if current not in used and (k - current) not in used:
                used.add(current)
                total += current
            current += 1
        
        return total

public class Solution {
    public int MinimumSum(int n, int k) {
        HashSet<int> used = new HashSet<int>();
        int sum = 0;
        int current = 1;
        
        while (used.Count < n) {
            if (!used.Contains(current) && !used.Contains(k - current)) {
                used.Add(current);
                sum += current;
            }
            current++;
        }
        
        return sum;
    }
}

var minimumSum = function(n, k) {
    const used = new Set();
    let sum = 0;
    let current = 1;
    
    while (used.size < n) {
        if (!used.has(current) && !used.has(k - current)) {
            used.add(current);
            sum += current;
        }
        current++;
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k)最坏情况下需要遍历约 n + k/2 个数字
空间复杂度O(n)使用哈希集合存储已选择的 n 个数字