构成特定和添加的最少元素【LC1785】

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Return the minimum number of elements you need to add to make the sum of the array equal to goal. The array must maintain its property that abs(nums[i]) <= limit.

Note that abs(x) equals x if x >= 0, and -x otherwise.

2022/12/16

跟LC1827最少操作数使数组递增这题很类似，还更简单些

• 思路：首先统计数组nums的和sum，然后计算sum与goal的差target，我们需要向数组中添加最少的元素，使元素的和满足差值，元素的个数即为最终结果，因此每次添加的元素应尽可能最大。由于添加数值的绝对值大小受limit限制，因此添加元素的数值绝对值为limit的个数为Math.abs(target)/limit，如果Math.abs(target)不等于0，那么还需添加一个元素使和等于target

【贪心】

。局部最优：每次添加的元素应尽可能最大

。全局最优：添加的元素个数最少

• 实现

为了防止越界使用long类型变量存储target

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long target = (long) goal;
        int count = 0;
        for (long num : nums){
            target -= num;
        }
        count += Math.abs(target) / limit;       
        return Math.abs(target) % limit == 0 ? count : count + 1;
    }
}

。复杂度

• 时间复杂度：O ( n )
• 空间复杂度：O ( 1 )