力扣第 283 场周赛：向数组中追加 K 个整数-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、问题描述

给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个未出现在 nums 中的、互不相同 的正整数，并使结果数组的元素和最小。

返回追加到 nums 中的 k 个整数之和。

二、题目要求

样例

输入： nums = [1,4,25,10,25], k = 2
输出： 5
解释： 在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
复制代码

考察

1.动态模拟
2.建议用时20~40min
复制代码

三、问题分析

一开始我是什么思路呢，就以样例为例，我先把样例从小到大排序：

1 4 10 25 25
复制代码

要求追加最小的数字，我就从一开始判断假如第一个数字为5，那么前面插入的优先顺序可以为1 2 3 4。样例的第一个数字是1，那我们就看1~ 4中间插入，还不满足 4~10中间插入……

到了最后如果还不满足，只能选取25之后的数字插入，直到满足条件，这个方法我觉得还是比较巧妙的，但提交超时了。

于是开启漫长的优化之路，思想还是上面的思想，但其实插入的数字和直接换成等差数列求和就优化成功了。

比如1~ 4中间有2 3 两个数字，k=10，需要2 3，k=8
4~10 中间有5 6 7 8 9四个数字，需要5 6 7 8 9，k=3
10~25中间有14个数字，但只需要11 12 13这三个,k=0，退出
复制代码

四、编码实现

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        long long int i,ans=0,sum=0,n=nums.size(),count,start,end;//初始化
        sort(nums.begin(),nums.end());//从小到大排序
        if(nums[i]>1)//第一个数字
        {
            start=1,end=nums[i]-1;//首位1,末位
            count=end-start+1;//中间数字的个数
            if(count>=k)//比需求的k还多
            {
                sum+=(start+start+k-1)*k/2;//只需要k个
                return sum;
            }
            else
                sum+=(start+end)*count/2;//比需求的少，全部都要
            k-=count;
        } 
        for(i=0;i<n-1;i++)//中间部分，两两组合
        {
            if(k==0)//退出循环条件
            {
                return sum;
            }
            if(nums[i+1]>nums[i])//中间有空
            {
                start=nums[i]+1,end=nums[i+1]-1;
                count=end-start+1;
                if(count>=k)
                {
                    sum+=(start+start+k-1)*k/2;//只需要k个
                    return sum;
                }
                else
                    sum+=(start+end)*count/2;//比需求的少，全部都要
                k-=count;
             }  
        }
        start=nums[n-1]+1;//最后一个数字
        sum+=(start+start+k-1)*k/2;//向后拓展
        return sum;//返回结果
    }  
};

复制代码