1658. Minimum Operations to Reduce X to Zero

Leetcode link

解题思路

本题要求我们用一个数组 nums 的两端之和组成整数 x

我们可以换个角度思考，首先求一个数 count 等于数组 nums 所有元素之和减去整数 x

我们就可以把问题转变为，找出数组中，长度之和为 count 的最长连续子串

因此，我们就可以用滑动窗口的思想来做题了

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int left = 0, right = 0;
        // nums 数组的每一项之和
        int arrSum = 0;
        for(int num :nums) {
            arrSum += num;
        }
        int count = arrSum - x;
        // 当前滑动窗口之和
        int sum = 0;
        // 题目所求的长度
        int res = -1;

        // 数组所有元素之和小于整数 x，不可能有结果
        if(count < 0) {
            return -1;
        }
        while(right < nums.size()) {
            sum += nums[right];
            while(sum > count) {
                sum -= nums[left++];
            }
            if(count == sum) {
                res = max(res, right - left + 1);
            }
            right++;
        }
        if(res == -1) {
            return -1;
        } else {
            return nums.size() - res;
        }
    }
};

Javascript

var minOperations = function(nums, x) {
    let left = 0, right = 0;
    // nums 数组的每一项之和
    let arrSum = nums.reduce((prev, cur)=> prev + cur, 0);
    let count = arrSum - x;
    // 当前滑动窗口之和
    let sum = 0;
    // 题目所求的长度
    let res = -1;

    // 数组所有元素之和小于整数 x，不可能有结果
    if(count < 0) {
        return -1;
    }
    while(right < nums.length) {
        sum += nums[right];
        while(sum > count) {
            sum -= nums[left++];
        }
        if(count === sum) {
            res = Math.max(res, right - left + 1);
        }
        right++;
    }
    if(res === -1) {
        return -1;
    } else {
        return nums.length - res;
    }

};