前往
大廳
主題

LeetCode - 1785. Minimum Elements to Add to Form a Given Sum 解題心得

Not In My Back Yard | 2024-04-16 12:00:05 | 巴幣 0 | 人氣 25

題目連結:


題目意譯:
你被給定一個整數陣列 nums 以及兩整數 limit 和 goal。陣列 nums 有著一個有趣的性質——abs(nums[i]) ≦ limit。

回傳為了使 nums 的元素總和等於 goal,你最少所需加入到 nums 的元素數量。該陣列必須依舊滿足其性質,即 abs(nums[i]) ≦ limit。

注意到 abs(x) 代表著如果 x ≧ 0,則其值等於 x;反之,則等於 -x。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ limit ≦ 10 ^ 6
-limit ≦ nums[i] ≦ limit
-10 ^ 9 ≦ goal ≦ 10 ^ 9



範例測資:
範例 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


解題思維:
假設現在 nums 的元素總和為 s,而與 goal 的差值之絕對值為 d = abs(s - goal)。

如果 d < limit,則我們直接新增 +d(或 -d)進 nums 即可;如果 d ≧ limit,則我們就一直新增 +limit(或 -limit)進去到 nums 中,將 d 減去 limit 直到 d < limit 為止(此時可以套用第一種情況)。

當然,直接照上面的做基本上會超時(例如說 d 是 10 ^ 9,但 limit 只有 1 之類的)。因此我們需要直接算出來,而公式很簡單:
(d + limit - 1) ÷ limit 取整數
即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作