Medium

题目描述

给你一个整数数组 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^5
  • 1 <= nums[i] <= 10^4
  • 1 <= x <= 10^9

解题思路

这道题的核心思路是逆向思考：与其直接寻找从左右两端删除元素使和为 x 的最少操作次数，不如转换为寻找中间连续子数组的最大长度，使得剩余元素的和等于 x。

解题思路

  1. 问题转换：如果我们从左右两端删除一些元素使得和为 x，那么剩余的中间部分必定是一个连续的子数组，其和为 total - x（其中 total 是数组总和）。

  2. 滑动窗口求解：问题转化为求和等于 total - x 的最长连续子数组。这可以用滑动窗口技术高效解决。

  3. 边界条件处理：

    • 如果 total < x，无解返回 -1
    • 如果 total == x，删除整个数组，返回数组长度
    • 如果找不到和为 total - x 的子数组，返回 -1

算法流程

  1. 计算数组总和 total
  2. 计算目标子数组和 target = total - x
  3. 使用滑动窗口寻找和为 target 的最长子数组
  4. 返回 n - maxLength（n 为数组长度，maxLength 为最长子数组长度）

推荐解法：滑动窗口 - 时间复杂度最优，代码简洁。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total < x) return -1;
        if (total == x) return nums.size();
        
        int target = total - x;
        int n = nums.size();
        int left = 0, sum = 0, maxLen = -1;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while (sum > target && left <= right) {
                sum -= nums[left++];
            }
            
            if (sum == target) {
                maxLen = max(maxLen, right - left + 1);
            }
        }
        
        return maxLen == -1 ? -1 : n - maxLen;
    }
};

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        total = sum(nums)
        if total < x:
            return -1
        if total == x:
            return len(nums)
        
        target = total - x
        n = len(nums)
        left = 0
        current_sum = 0
        max_len = -1
        
        for right in range(n):
            current_sum += nums[right]
            
            while current_sum > target and left <= right:
                current_sum -= nums[left]
                left += 1
            
            if current_sum == target:
                max_len = max(max_len, right - left + 1)
        
        return -1 if max_len == -1 else n - max_len

public class Solution {
    public int MinOperations(int[] nums, int x) {
        int total = nums.Sum();
        if (total < x) return -1;
        if (total == x) return nums.Length;
        
        int target = total - x;
        int n = nums.Length;
        int left = 0, sum = 0, maxLen = -1;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            while (sum > target && left <= right) {
                sum -= nums[left++];
            }
            
            if (sum == target) {
                maxLen = Math.Max(maxLen, right - left + 1);
            }
        }
        
        return maxLen == -1 ? -1 : n - maxLen;
    }
}

var minOperations = function(nums, x) {
    const n = nums.length;
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    const target = totalSum - x;
    
    if (target < 0) return -1;
    if (target === 0) return n;
    
    let left = 0;
    let currentSum = 0;
    let maxLength = -1;
    
    for (let right = 0; right < n; right++) {
        currentSum += nums[right];
        
        while (currentSum > target && left <= right) {
            currentSum -= nums[left];
            left++;
        }
        
        if (currentSum === target) {
            maxLength = Math.max(maxLength, right - left + 1);
        }
    }
    
    return maxLength === -1 ? -1 : n - maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(1)
  • 时间复杂度：O(n)，其中 n 是数组长度。虽然有嵌套循环，但每个元素最多被访问两次（right 指针和 left 指针各一次）。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。

相关题目