1658. 将 x 减到 0 的最小操作数#

题目描述#

给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。

如果可以将 x 恰好减到 0，返回最小操作数；否则，返回 -1。

核心思想#

正难则反 + 不定长滑动窗口。

从两端移除元素使和为 x，等价于在数组中间找一个最长子数组，其和为 total - x。

设 target = total - x：

若 target < 0：无解，返回 -1
若 target == 0：需移除全部元素，返回 n
否则：用滑动窗口找和为 target 的最长子数组，答案 = n - 最长子数组长度

算法步骤#

计算 total = sum(nums), target = total - x
特判 target < 0 返回 -1，target == 0 返回 n
初始化 left = 0, window = 0, ans = -1
遍历 right 从 0 到 n-1：
- window += nums[right]
- 当 window > target 时：window -= nums[left], left += 1
- 若 window == target：ans = max(ans, right - left + 1)
若 ans == -1 返回 -1，否则返回 n - ans

逐步举例#

以 nums = [1, 1, 4, 2, 3], x = 5 为例：

total = 11, target = 11 - 5 = 6

right	nums[right]	window	>6?	收缩	left	window==6?	ans
0	1	1	否	—	0	否	-1
1	1	2	否	—	0	否	-1
2	4	6	否	—	0	是	3
3	2	8	是	l=1, window=7; l=2, window=6	2	是	3
4	3	9	是	l=3, window=5	3	否	3

最终 ans = 3（子数组 [1,1,4]），返回 5 - 3 = 2。

验证：移除两端 [2, 3]，和 = 5 ✓，操作数 = 2。

复杂度分析#

时间复杂度：O(n)。每个元素最多进出窗口各一次。
空间复杂度：O(1)。

参考#

灵茶山艾府：将 x 减到 0 的最小操作数

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def minOperations(self, nums: List[int], x: int) -> int:
6
        total = sum(nums)
7
        target = total - x
8
        if target < 0:
9
            return -1
10
        if target == 0:
11
            return len(nums)
12

13
        n = len(nums)
14
        ans = -1
15
        left = window = 0
16
        for right in range(n):
17
            window += nums[right]
18
            while window > target:
19
                window -= nums[left]
20
                left += 1
21
            if window == target:
22
                ans = max(ans, right - left + 1)
23
        return -1 if ans == -1 else n - ans

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6

7
from solution import Solution
8

9

10
class TestMinOperations(unittest.TestCase):
11
    def test_example1(self):
12
        nums = [1, 1, 4, 2, 3]
13
        x = 5
14
        self.assertEqual(Solution().minOperations(nums, x), 2)
15

16
    def test_example2(self):
17
        nums = [5, 6, 7, 8, 9]
18
        x = 4
19
        self.assertEqual(Solution().minOperations(nums, x), -1)
20

21
    def test_example3(self):
22
        nums = [3, 2, 20, 1, 1, 3]
23
        x = 10
24
        self.assertEqual(Solution().minOperations(nums, x), 5)
25

26
    def test_remove_all(self):
27
        nums = [1, 2, 3]
28
        x = 6
29
        self.assertEqual(Solution().minOperations(nums, x), 3)
30

31
    def test_remove_first(self):
32
        nums = [5, 2, 3, 1, 1]
33
        x = 5
34
        self.assertEqual(Solution().minOperations(nums, x), 1)
35

36
    def test_single_element(self):
37
        nums = [1]
38
        x = 1
39
        self.assertEqual(Solution().minOperations(nums, x), 1)
40

41
    def test_single_element_impossible(self):
42
        nums = [1]
43
        x = 2
44
        self.assertEqual(Solution().minOperations(nums, x), -1)
45

46

47
if __name__ == "__main__":
48
    unittest.main()