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

题目描述

leetcode 中等题

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

提示1：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
1 <= x <= 10^9

双指针 + 前缀和

首先由于每次都是从最左边或最右边选择一个元素，那么 $x$ 必然由数组的一个前缀、后缀所组成。

因此原题目可以转化成求元素和为 $sum - x$ 的子数组，其中 $sum$ 为数组总和，此时的操作次数显然为数组长度减去子数组长度。

具体可以使用双指针 + 前缀和的方式进行求解。为了方便，初始时将 $x$ 转换成 $sum - x$，左右指针均指向 $0$，右指针每次向右移动一位，并将当前指向元素累加到前缀和 $curSum$ 中，而每当 $curSum$ 大于 $x$ 时，向右移动左指针并从前缀和中减去当前指向元素，直到 $curSum <= x$ ，此时再尝试更新 $ans$ 即可。

class Solution {

    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        // x = sum - x
        x = -x;
        x = Arrays.stream(nums).reduce(x, Integer::sum);
        int ans = n + 1;
        for(int left = 0, right = 0, curSum = 0; right < n; right++){
            curSum += nums[right];
            while(left <= right && curSum > x){
                curSum -= nums[left++];
            }
            if(curSum == x){
                ans = Math.min(ans, n - (right - left + 1));
            }
        }
        return ans == n + 1 ? -1 : ans;
    }

}

类似的做法还可以使用哈希表：

class Solution {

    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        // x = sum - x
        x = -x;
        x = Arrays.stream(nums).reduce(x, Integer::sum);
        Map<Integer, Integer> sumMapIndex = new HashMap<>();
        sumMapIndex.put(0, -1);
        int ans = n + 1;
        for(int i = 0, preSum = 0; i < n; i++){
            preSum += nums[i];
            sumMapIndex.put(preSum, i);
            if(sumMapIndex.containsKey(preSum - x)){
                ans = Math.min(ans, n - (i - sumMapIndex.get(preSum - x)));
            }
        }
        return ans == n + 1 ? -1 : ans;
    }

}