[LeetCode] 1785. Minimum Elements to Add to Form a Given Sum

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.

Example 1:

Input: nums = [1,-1,1], limit = 3, goal = -4
Output: 2
Explanation: You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.

Example 2:

Input: nums = [1,-10,9,1], limit = 100, goal = 0
Output: 1

Constraints:

• 1 <= nums.length <= 105
• 1 <= limit <= 106
• -limit <= nums[i] <= limit
• -109 <= goal <= 109

构成特定和需要添加的最少元素。

给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性：abs(nums[i]) <= limit 。

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

注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题的思路是贪心。首先我们需要求 nums 数组所有数字的总和，记为 curSum。然后我们看一下 curSum 和 goal 之间的差值，记为 diff。为了方便，我在代码中将 diff 取了绝对值。注意题目让我们返回的是添加的元素的数量，这里我看一下 diff 和 limit 取模是否等于 0，如果不等于 0 ，count就需要 + 1。注意题目中有的 case 会使得 diff 超过 integer 的范围，所以记录的时候需要用 long 型。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minElements(int[] nums, int limit, int goal) {
 3         long curSum = 0;
 4         for (int num : nums) {
 5             curSum += num;
 6         }
 7 
 8         // corner case
 9         if (curSum == goal) {
10             return 0;
11         }
12         // normal case
13         long diff = Math.abs(goal - curSum);
14         long count = 0;
15         if (diff <= limit) {
16             count = 1;
17         } else {
18             if (diff % limit == 0) {
19                 count = diff / limit;
20             } else {
21                 count = diff / limit + 1;
22             }
23         }
24         return (int) count;
25     }
26 }

LeetCode 题目总结