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

Posted on

題目在此 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

相關文章