中等

问题描述

给你一个整数数组 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$ 的前缀和与其对应数字的个数，然后从后往前尝试移除的元素，记录移除元素之和，并且在前缀记录中查找是否存在 $x$ 与移除元素和的差值，若存在，则计算此方式移除元素的个数，并与历史移除元素个数记录作比较取较小值。

/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function (nums, x) {
  const n = nums.length
  const prefix = new Map()
  let sum = 0
  for (let i = 0; i < n; i++) {
    sum += nums[i]
    prefix.set(sum, i + 1)
  }
  if (sum < x) return -1
  let ans = prefix.get(x) ?? n + 1
  sum = 0
  for (let cnt = 1; cnt <= n; cnt++) {
    sum += nums[n - cnt]
    if (sum > x) break
    if (x - sum === 0) {
      ans = Math.min(ans, cnt)
    } else if (prefix.has(x - sum)) {
      ans = Math.min(ans, prefix.get(x - sum) + cnt)
    }
  }
  return ans > n ? -1 : ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$