LC 1785. 构成特定和需要添加的最少元素

题目描述

这是 LeetCode 上的 1785. 构成特定和需要添加的最少元素 ,难度为 中等

给你一个整数数组 nums,和两个整数 limitgoal

数组 nums 有一条重要属性:abs(nums[i]) <= limit

返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ,添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。

注意,如果 x >= 0,那么 abs(x) 等于 x ;否则,等于 -x

示例 1:

1
2
3
4
5
输入:nums = [1,-1,1], limit = 3, goal = -4

输出:2

解释:可以将 -2-3 添加到数组中,数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4

示例 2:
1
2
3
输入: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 而言,我们可以先通过 $O(n)$ 的遍历求得其原总和 sum 为何值。

sumgoal 不等,我们可以按照「贪心」的方式里添加元素。

由于添加的元素需要满足 abs(x) <= limit 要求,因此我们添加数的范围在 $[-limit, limit]$ 之间。

为确保添加的元素最小,我们应当优先添加能够有效抵消两者差值的数值(添加 $limit$ 或 $-limit$),添加个数为 $\left \lceil \frac{\left | sum - goal \right |}{limit} \right \rceil$。

Java 代码:

1
2
3
4
5
6
7
class Solution {
public int minElements(int[] nums, int limit, int goal) {
long sum = 0;
for (int x : nums) sum += x;
return (int) ((Math.abs(sum - goal) + limit - 1) / limit);
}
}

TypeScript 代码:
1
2
3
4
5
function minElements(nums: number[], limit: number, goal: number): number {
let sum = 0
for (const x of nums) sum += x
return Math.ceil(Math.abs(sum - goal) / limit)
}

Python 代码:
1
2
3
4
class Solution:
def minElements(self, nums: List[int], limit: int, goal: int) -> int:
sumv = sum(nums)
return (abs(sumv - goal) + limit - 1) // limit

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1785 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!