当前位置：首页 > article >正文

2.4滑动窗口专题：将 x 减到 0 的最小操作数

article 2025/3/16 15:26:59

题目分析与算法对比（LeetCode 1658. 将 x 减到 0 的最小操作数）

1. 题目链接

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

2. 题目描述

给定一个整数数组 nums 和一个整数 x，每次操作可以从数组的最左侧或最右侧删除一个元素，返回使数组元素和减少到 x 所需的最小操作次数。若无法达成，返回 -1。
示例1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
示例2：
输入：nums = [5,6,7,8,9], x = 4
输出：2

3. 算法思路

问题转化：
题目要求从两端删除元素使得总和减少到 x，等价于寻找一个中间连续子数组，使得该子数组的和等于 total - x（total 为数组总和），此时需要删除的子数组外部的元素数目即为操作次数。
核心目标：找到最长的中间子数组，其和为 total - x，从而最小化操作次数（即 n - 子数组长度）。

滑动窗口法：

初始化：计算数组总和 total，得到目标子数组和 target = total - x。
边界处理：若 target < 0，直接返回 -1；若 target = 0，返回 n（需删除全部元素）。
滑动窗口：
- 右指针 right 不断扩展窗口，累加当前窗口和 sum。
- 当 sum > target 时，左指针 left 右移以缩小窗口。
- 当 sum = target 时，记录当前窗口长度并更新最大值。
结果计算：最终结果为 n - 最长子数组长度，若无解则返回 -1。

4. 代码实现

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int n = nums.size();
        int total = 0;
        for(auto it : nums)   total += it;
        int target = total - x;
        // 边界处理
        if(target < 0) return -1;
        if(target == 0) return n;

        int left = 0, right = 0, sum = 0, MaxSubstringLength = -1;
        for(right = 0; right < n; right++)
        {
            // 进窗口
            sum += nums[right];
            // 判断并出窗口
            while(sum > target && left < right) sum -= nums[left++];
            // 跟新结果
            if(sum == target) 
            	MaxSubstringLength = max(MaxSubstringLength,right - left + 1);
        }
        return MaxSubstringLength == -1 ? -1 : n - MaxSubstringLength;
    }
};

在这里插入图片描述

5. 暴力枚举法与滑动窗口法对比图表

对比维度	暴力枚举法	滑动窗口法
核心思想	遍历所有可能的子数组组合，检查其和是否等于 `target`，记录最长长度。	动态维护窗口，保证窗口和始终 ≤ `target`，仅在窗口和等于 `target` 时更新结果。
时间复杂度	O(n²)（枚举所有子数组起点和终点，共 n(n+1)/2 次操作）。	O(n)（每个元素被左右指针各访问一次）。
空间复杂度	O(1)（无需额外存储）。	O(1)（仅需常数变量记录窗口状态）。
实现方式	双重循环嵌套，计算每个子数组的和。	单层循环扩展右指针，内层循环收缩左指针。
适用场景	小规模数据（n ≤ 1e3）。	大规模数据（n ≤ 1e5）。
优点	逻辑简单，直接穷举所有可能解。	时间复杂度低，适用于大规模数据。
缺点	数据规模大时性能极差（n=1e4 时需 1e8 次操作）。	仅适用于数组元素全为非负数的场景（若含负数需改用前缀和+哈希表）。