LeetCode 筆記 - 1658. Minimum Operations to Reduce X to Zero

題目在此 1658. Minimum Operations to Reduce X to Zero

給定一個數列與目標 x,你可以從數列挑選最左邊或最右邊的元素讓 x 減,直到使 x 等於 0
請計算出最小步驟!

解題思維

這題從最左最右開始,很直覺的感覺可以用 Two Pointers 大法

如果直接計算左右的移除元素 = x,會發現其實有蠻多特殊情況要考慮
此時我們可以反過來找 移除後數列總和 = 原始總和 - x,會比較好實作一點

剩下就是使用了 Prefix Sum 來加速計算總和

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:

if (total := sum(nums)) < x:
return -1

size = len(nums)

if total == x:
return size

count = collections.defaultdict(int)
temp = 0
for i in range(size):
temp += nums[i]
count[i] = temp

target = total - x
start = 0

result = size
for end in range(size):

while True:
value = count[end] - count[start - 1]

if value == target:
result = min(result, start + (size - end - 1))
break
elif value < target:
break
start += 1
if start > end:
break

if result == size:
return -1
return result