Medium

题目描述

给你一个整数数组 nums 和两个整数 limit 和 goal。数组 nums 有一个有趣的特性：abs(nums[i]) <= limit。

返回使数组元素之和等于 goal 所需要向数组中添加的最少元素数目。添加的元素同样需要满足 abs(nums[i]) <= limit。

注意，abs(x) 等于 x（如果 x >= 0），否则等于 -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 <= 10^5
  • 1 <= limit <= 10^6
  • -limit <= nums[i] <= limit
  • -10^9 <= goal <= 10^9

解题思路

这是一道贪心算法题目。我们需要分析问题的核心：

  1. 问题转化：首先计算当前数组的和 currentSum，那么我们需要添加的元素总和应该是 diff = goal - currentSum。

  2. 贪心策略：为了使添加的元素数量最少，我们应该让每个添加的元素尽可能大（绝对值）。由于限制是 abs(nums[i]) <= limit，所以：

    • 如果 diff > 0，我们应该尽量添加 limit
    • 如果 diff < 0，我们应该尽量添加 -limit

  3. 计算方法：需要添加的元素个数就是 ceil(abs(diff) / limit)，用整数除法表示就是 (abs(diff) + limit - 1) / limit。

  4. 特殊情况：如果 diff = 0，说明当前和已经等于目标，不需要添加任何元素。

这个解法的时间复杂度是 O(n)，因为需要遍历数组计算和；空间复杂度是 O(1)。

代码实现

class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long currentSum = 0;
        for (int num : nums) {
            currentSum += num;
        }
        
        long long diff = abs(goal - currentSum);
        return (diff + limit - 1) / limit;
    }
};

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        current_sum = sum(nums)
        diff = abs(goal - current_sum)
        return (diff + limit - 1) // limit

public class Solution {
    public int MinElements(int[] nums, int limit, int goal) {
        long currentSum = 0;
        foreach (int num in nums) {
            currentSum += num;
        }
        
        long diff = Math.Abs(goal - currentSum);
        return (int)((diff + limit - 1) / limit);
    }
}

var minElements = function(nums, limit, goal) {
    const currentSum = nums.reduce((sum, num) => sum + num, 0);
    const diff = Math.abs(goal - currentSum);
    return Math.ceil(diff / limit);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 是数组 nums 的长度。时间复杂度主要来自于计算数组和的遍历过程，空间复杂度为常数级别。