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元起，快前往官网查看详情吧