1658. Minimum Operations to Reduce X to Zero

Question

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return *the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return *-1.

Solution

将原有问题的从两边减去一定的值，寻找加和为x的问题转换为寻找滑动窗口中的总和为total - x的新问题。

滑动窗口

初始化当前窗口内的sum，左侧指针left与右侧指针right。
每次将一个新的元素nums[right]加入窗口范围。

当当前的sum大于寻找的target，则将nums[left]滑出窗口，更新left与sum的值。

如果当前窗口内的sum等于寻找的target，则更新记录最小操作次数的min。

Code

class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0, min = Integer.MAX_VALUE;
        for(int num : nums){
            total += num;
        }
        int target = total - x; //将减去两侧元素并寻找和为x的结果的问题转换为用滑动窗口寻找total - x的结果。
        int sum = 0, left = 0, right = 0;
        while(right < nums.length){
            sum += nums[right]; //调整右侧范围，加入新元素到窗口
            right++;
            
            while(left < right && sum > target){ //如果窗口内的和大于目标，则调整左侧范围
                sum -= nums[left];
                left++;
            }
            if(sum == target){   //如果窗口内的和等于目标，则更新最小操作次数
                min = Math.min(min, nums.length - (right - left));
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}