LeetCode题目笔记——1658. 将 x 减到 0 的最小操作数

• 我把这篇也归到面试题那一栏，因为觉得这题的思路和思考方式还挺好的，或许能用到其他题上

题目描述

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

• 提示：

  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁴
  • 1 <= x <= 10⁹

题目链接

题目难度——中等

方法一：反向思考，双指针求最长子数组

  仔细看，屏幕上的这个题目。 仔细审题，题目要求每次删除数组首或尾的元素并将x减去这个值，直到x为0，求这个删除操作的最小次数。换一个说法，不就是求最少的首部和尾部的元素之和为x的元素个数吗，所以我们可以先对数组求和，记为total，再进一步，题目就变成求和为total - x的最长子数组，于是就可以用双指针来做。
  这里虽然想到了这个办法，但是因为双指针的经验不多，所以借鉴了一下讨论区里一个大佬的代码思路，大佬的题解传送门。

代码/Python

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)
        total = sum(nums)	# 实测这里将sum函数换成for循环手动求和的话，结果会快很多
        target = total - x
        if target < 0:
            return -1
        res = -1
        p1 = total = 0
        for p2 in range(n):
            total += nums[p2]
            while total > target:
                total -= nums[p1]
                p1 += 1
            
            if total == target:
                res = max(res, p2 - p1 + 1)

        return -1 if res < 0 else n - res

代码/C++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size(), target, p1, p2, res, total;
        p1 = total = 0, res = -1;
        while(p1 < n){
            total += nums[p1++];
        }
        target = total - x;
        if(target < 0){
            return -1;
        }
        total = p1 = 0;
        for(p2 = 0; p2 < n; p2++){
            total += nums[p2];
            while(total > target){
                total -= nums[p1++];
            }
            if(total == target){
                res = max(res, p2 - p1 + 1);
            }
        }
        return res < 0 ? -1 : n - res;
    }
};

方法二：滑动窗口

  其实滑动窗口的思路跟上面那个差不多，只不过滑动窗口是正向思路，顺着题目的意思。具体的，同样先求和total，如果total < x，即整体都不够x，肯定无法满足要求。这里直接引用官方的滑动窗口题解，官方链接

代码

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)
        total = 0
        for num in nums:
        	total += num
        if total < x:
            return -1
        
        right = 0
        lsum, rsum = 0, total
        res = n + 1
        for left in range(-1, n - 1):
            if left != -1:
                lsum += nums[left]
            while right < n and lsum + rsum > x:
                rsum -= nums[right]
                right += 1
            
            if lsum + rsum == x:
                res = min(res, left + 1 + n - right)
        
        return res if res <= n else -1

总结

  两种方法一个正向，一个反向，个人觉得反向的思路要更好一点，更容易理解一些，都需要遍历一遍，所以时间是O(N)，都只用到了常量变量，所以空间是O(1)。