跳转至

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

问题描述#

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

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

 

示例 1：


输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：


输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：


输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

解题思路#

广搜会超时。

结果有三种情况：

  • 只从左边移除元素
  • 只从右边移除元素
  • 两边都有元素移除

因为数组元素都是正数，所以累计和是递增的有序数组。

所以可以先用字典记录后缀和的下标，然后从左边遍历前缀和数组。

 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
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        len_nums = len(nums)
        front, t = [0], 0
        # 前缀和
        for i, num in enumerate(nums):
            t += num
            if t > x:
                break
            front.append(t)

        # 后缀和
        back, t = {}, 0
        for i, num in enumerate(nums[::-1]):
            t += num
            if t > x:
                break
            back[t] = i + 1

        ans = float("INF")
        for i, num in enumerate(front):
            if num == x:
                ans = min(ans, i)
                break
            idx = back.get(x - num, float("INF"))
            if i + idx <= len_nums: # 不能超过数组长度
                ans = min(ans, idx + i)

        return -1 if ans == float("INF") else ans
测试数据
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
solution = Solution()

nums = [1, 1, 4, 2, 3]
x = 5
assert solution.minOperations(nums, x) == 2

nums = [5, 6, 7, 8, 9]
x = 4
assert solution.minOperations(nums, x) == -1

nums = [3, 2, 20, 1, 1, 3]
x = 10
assert solution.minOperations(nums, x) == 5

print("PASS")
返回顶部

在手机上阅读