构成特定和添加的最少元素【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 )