leetcode-1785-构成特定和需要添加的最少元素-创新互联
给你一个整数数组nums，和两个整数limit与goal。数组nums有一条重要属性：abs(nums[i])<= limit。
返回使数组元素总和等于goal所需要向数组中添加的 最少元素数量 ，添加元素 不应改变 数组中abs(nums[i])<= limit这一属性。
注意，如果x >= 0，那么abs(x)等于x；否则，等于-x。
示例 1：
输入：nums = [1,-1,1], limit = 3, goal = -4
输出：2
解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。
示例 2：
输入：nums = [1,-10,9,1], limit = 100, goal = 0
输出：1
提示：
- 1<= nums.length<= 10^5
- 1<= limit<= 10^6
- -limit<= nums[i]<= limit
- -10^9<= goal<= 10^9
分析：
看到这道题，第一反应就是把nums中的数加起来，然后用加起来的值和goal的差值除以limit即可得到结果。
class Solution {public:
int minElements(vector& nums, int limit, int goal) {int addnum = 0;
for(auto num : nums)
addnum += num;
int gapnum = goal - addnum;
return (abs(gapnum) - 1)/abs(limit) + 1;
}
}; 很遗憾只能满足65 / 77 个通过测试用例。原因在于后面的测试用例中nums的和非常大，超出了int所能表示的范围，因此我们还要考虑其他的方式。
为了防止超出范围，我想到了一个方法：
在nums求和的过程中，想办法让和的绝对值小于limit，我们可以通过给这个和加上或者减去limit来实现这个效果，并分别记录加上和减去的次数，这个次数在后面是可以相互抵消的。
依照这个思路可得到如下代码：
class Solution {public:
int minElements(vector& nums, int limit, int goal) {int addnum = 0;//nums的和(其中加上和减去了多个limit)
int minustimes = 0;//减limit次数
int plustimes = 0;//加limit次数
for(auto num : nums){addnum += num;
if(addnum >= limit){//过大则减
addnum -= limit;
++minustimes;
}
if(addnum<= -limit){//过小则加
addnum += limit;
++plustimes;
}
}
int gapnum = goal - addnum;//goal与addnum的差值
if(gapnum == 0)//正好为0时，可直接返回差值
return abs(minustimes - plustimes);
int remaintimes = (abs(gapnum) - 1)/abs(limit) + 1;//加减limit后还需limit的个数
int totaltimes = 0;//总次数
if(gapnum >0){//gapnum大于0时，remaintimes为加的次数
totaltimes = abs(remaintimes + plustimes - minustimes);
}else{//gapnum小于0时，remaintimes为减的次数
totaltimes = abs(remaintimes + minustimes - plustimes);
}
return totaltimes;
}
}; 执行用时：88 ms, 在所有 C++ 提交中击败了92.20%的用户
内存消耗：71.6 MB, 在所有 C++ 提交中击败了78.72%的用户
通过测试用例：77 / 77
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页名称：leetcode-1785-构成特定和需要添加的最少元素-创新互联
URL网址：http://mswzjz.cn/article/coedjg.html