将 x 减到 0 的最小操作数

题目

题目来源：力扣（LeetCode）

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

思路分析

题意转换：每次都从数组开头或结尾进行取数，而最终x变为0，即从开头或结尾取出来的数总和为x

1. 可以使用前缀和解答；前缀和就是这个数组i元素前面的所有的元素相加之和。
2. 具体可以把解分成三部分：只取左半部分的和，只取右半部分的和，取左右两部分的和
3. 前缀和就是用来解决，区间和，就是从左边数前缀和，从右边数前缀和。又因为数组中没有负数，所 以前缀和一定是个有序数组，所以处理出两个前缀和、后缀和数组，sumLeft 、sumRight这两个数组肯 定都是单调的，一定是个有序数据，递增的。
4. 遍历是左边的前缀和里面的每个值，再到右边前缀和里面的值去查找，查找剩余部分是否存在

var minOperations = function (nums, x) {
    let sumL = new Array(nums.length + 1);
    let sumR = new Array(nums.length + 1);
    sumL[0] = sumR[0] = 0;
    // 计算左前缀和
    for (let i = 0; i < nums.length; i++) {
        sumL[i + 1] = sumL[i] + nums[i];
    }
    // 计算右前缀和
    for (let i = nums.length - 1; i >= 0; --i) {
        sumR[nums.length - i] = sumR[nums.length - i - 1] + nums[i];
    }
    let ans = -1;
    for (let i = 0; i < sumL.length; i++) {
        let j = binarySearch(sumR, x - sumL[i]);//查找剩余数量
        if (j == -1) continue;
        if (i + j > nums.length) continue;
        if (ans == -1 || ans > i + j) ans = i + j;
    }
    return ans;
};
// 二分查找
var binarySearch = function (nums, x) {
    let head = 0, tail = nums.length - 1, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (nums[mid] == x) return mid;
        if (nums[mid] < x) head = mid + 1;
        else tail = mid - 1;
    }
    return -1
}