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

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

• 滑动窗口

function minOperations(nums: number[], x: number): number {

    const sum: number = nums.reduce((total, value) => total + value, 0),
        target: number = sum - x;

    if (target < 0) {
        return -1;
    }

    let left: number = 0,
        right: number = 0,
        current: number = 0,
        min: number = nums.length + 1;

    while (left <= right && right <= nums.length) {

        while (right < nums.length && current < target) {
            current += nums[right];
            ++right;
        }

        if (current < target) {
            break;
        }

        if (current === target) {
            min = Math.min(min, nums.length - right + left);
        }

        current -= nums[left];
        ++left;

    }

    return min > nums.length ? -1 : min;

};

• 滑动窗口(更简洁)

/**
 *
 * @see https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/comments/771695
 * @param {number[]} nums
 * @param {number} x
 * @return {*}  {number}
 */
function minOperations(nums: number[], x: number): number {

    const sum: number = nums.reduce((total, value) => total + value, 0),
        target: number = sum - x;

    if (target < 0) {
        return -1;
    }

    let left: number = 0,
        right: number = 0,
        current: number = 0,
        min: number = nums.length + 1;

    while (right < nums.length) {

        current += nums[right];

        while (left < right && current > target) { // 太大了,要缩小
            current -= nums[left];
            ++left;
        }

        if (current === target) {
            min = Math.min(min, nums.length - (right - left + 1));
        }

        ++right;
    }

    return min > nums.length ? -1 : min;
};

• 哈希表

/**
 *
 * @see https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/comments/771695
 * @param {number[]} nums
 * @param {number} x
 * @return {*}  {number}
 */
function minOperations(nums: number[], x: number): number {

    const map: {} = { 0: -1 };

    let sum: number = 0;

    for (let i = 0; i < nums.length; ++i) {
        sum += nums[i];
        map[sum] = i;
    }

    if (sum < x) { // 数组的和还没x大
        return -1;
    }

    let leftSum: number,
        right: number = 0,
        currentSum: number = 0,
        min: number = nums.length + 1;

    while (right < nums.length) {

        currentSum += nums[right];
        leftSum = currentSum - (sum - x);

        if (leftSum in map) {
            const left: number = map[leftSum];
            min = Math.min(min, nums.length - right + left);
        }

        ++right;

    }

    return min > nums.length ? -1 : min;

};