LeetCode_贪心算法_中等_1785.构成特定和需要添加的最少元素

迷南。 2023-10-07 22:11 4阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 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 <= 105  
1 <= limit <= 106  
\-limit <= nums\[i\] <= limit  
\-109 <= goal <= 109

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum

## 2.思路 ##

（1）贪心算法  
① 遍历数组 nums ，用变量 sum 保存其元素和；  
② 用变量 diff = Math.abs(goal - sum) 来表示当前总和与目标总和之间的差距；  
③ 由于添加的元素所要满足的范围为 -limit <= nums\[i\] <= limit，它是关于 0 对称的，因此当 sum > goal 时添加负数的情况可以被当作 sum < goal 时添加正数来处理，那么接下来就只需要计算使用多少个小于等于 limit 的数来凑齐 diff，一共分为以下两种情况：  
1）diff % limit == 0，那么答案就是 diff / limit；  
2）diff % limit == 0，那么答案就是 diff / limit + 1；

> 注意：在累加求 sum 时，由于可能出现**整数溢出**问题，因此在下面的代码中，sum 的类型为 long。

## 3.代码实现（Java） ##

//思路1————贪心算法
    class Solution {
        
        public int minElements(int[] nums, int limit, int goal) {
        
            int res = 0;
            long sum = 0;
            for (int num : nums) {
        
                sum += num;
            }
            long diff = Math.abs(goal - sum);
            if (diff % limit == 0) {
        
                res = (int) (diff / limit);
            } else {
        
                res = (int) (diff / limit + 1);
            }
            return res;
        }
    }