题目

给你一个整数数组 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

解题思路

首先正序遍历和逆序遍历一遍数组nums,将遍历到的每个元素累加保存进’leftSum’和’rightSum’中。
在累加元素的过程中我们可以判断一下是否有==x的情况出现，若出现：

  1. 正序遍历 ans = min(ans, i + 1) ans为操作次数，n为数组长度，i为下标
  2. 逆序遍历 ans = min(ans, n - i)

接下来遍历我们的前缀和数组leftSum和rightSum
遍历过程中若发现leftSum[left] > x的情况则直接跳出大循环
以leftSum[left]为左边的起点，我们使用二分查找，查找rightSum能和左起点相加为x的下标：

  1. 若==x ans = min(ans, left + 1 + n - mid)

  2. 若 < x r = mid - 1

  3. 若 > x l = mid + 1

代码

Python

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:
        n = len(nums)
        ans = inf
        leftSum, rightSum = [0] * n, [0] * n
        for i in range(0, n):
            if i == 0: leftSum[i] = nums[i]
            else: leftSum[i] = leftSum[i - 1] + nums[i]
            if leftSum[i] == x: ans = min(ans, i + 1)
        for i in range(n - 1, -1, -1):
            if i == n - 1: rightSum[i] = nums[i]
            else: rightSum[i] = rightSum[i + 1] + nums[i]
            if rightSum[i] == x: ans = min(ans, n - i)

        for left in range(0, n):
            right = n - 1
            l = left + 1
            if leftSum[left] > x: break
            while l <= right:
                mid = ((right - l) >> 1) + l
                if leftSum[left] + rightSum[mid] == x:
                    ans = min(ans, left + 1 + n - mid)
                    break
                elif leftSum[left] + rightSum[mid] < x:
                    right = mid - 1
                else:
                    l = mid + 1
        return -1 if ans == inf else ans

Go

func minOperations(nums []int, x int) int {
    n := len(nums)
    ans := math.MaxInt64
    leftSum := make([]int, n, n)
    rightSum := make([]int, n, n)
    for i := 0; i < n; i++ {
        if i == 0 {
            leftSum[i] = nums[i]
        } else {
            leftSum[i] = leftSum[i - 1] + nums[i]
        }
        if leftSum[i] == x {ans = min(ans, i + 1)}
    }
    for i := n - 1; i >= 0; i-- {
        if i == n - 1 {
            rightSum[i] = nums[i]
        } else {
            rightSum[i] = rightSum[i + 1] + nums[i]
        }
        if rightSum[i] == x {ans = min(ans, n - i)}
    }
    for left := 0; left < n; left++ {
        right := n - 1
        if leftSum[left] > x {break}
        l := left + 1
        for l <= right {
            mid := ((right - l) >> 1) + l
            if leftSum[left] + rightSum[mid] == x {
                ans = min(ans, left + 1 + n - mid)
                break
            } else if leftSum[left] + rightSum[mid] < x {
                right = mid - 1
            } else {
                l = mid + 1
            }
        }
    }
    if ans != math.MaxInt64 {return ans}
    return -1
}

func min(a int, b int) int {
    if a > b {return b}
    return a
}