**LeetCode 1658详解：滑动窗口求减到零的最小操作数**

LeetCode 1658题是一个典型的最优化问题，要求找到将x减到0的最小操作数。这个问题可以通过巧妙的数学转换和滑动窗口技术高效解决。

### 问题描述与理解

题目要求：给定一个整数数组nums和一个整数x，每次操作可以从数组的最左边或最右边移除一个元素，并减去该元素的值。返回将x恰好减到0的最小操作数，如果无法实现则返回-1。

```c

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

// 函数声明

int minOperations(int* nums, int numsSize, int x);

void testCases();

// 打印数组

void printArray(int* nums, int numsSize) {

    printf("[");

    for (int i = 0; i < numsSize; i++) {

        printf("%d", nums[i]);

        if (i < numsSize - 1) printf(", ");

    }

    printf("]");

}

```

### 问题分析与思路转换

关键思路：将问题转换为在数组中找到最长的子数组，使得子数组的和等于 `total_sum - x`。

```c

// 思路解析函数

void problemAnalysis() {

    printf("=== 问题分析 ===\n");

    printf("原始问题：从数组两端移除元素，使移除的元素和等于x\n");

    printf("等价转换：在数组中找到最长的子数组，使得子数组的和等于 total_sum - x\n");

    printf("原因：移除的元素和 = x ↔ 剩余的子数组和 = total_sum - x\n");

    printf("最小操作数 = 数组长度 - 最长子数组长度\n\n");

    

    printf("示例分析：\n");

    printf("nums = [1,1,4,2,3], x = 5\n");

    printf("total_sum = 11, target = 11 - 5 = 6\n");

    printf("最长子数组 [1,4,1] 和为6，长度=3\n");

    printf("最小操作数 = 5 - 3 = 2\n");

}

```

### 滑动窗口解法实现

滑动窗口是解决这类子数组和问题的经典方法。

```c

// 滑动窗口解法

int minOperations(int* nums, int numsSize, int x) {

    // 计算数组总和

    int total_sum <"7P.4961.HK">= 0;

    for (int i = 0; i < numsSize; i++) {

        total_sum += nums[i];

    }

    

    // 目标子数组和

    int target = total_sum - x;

    

    // 边界情况处理

    if (target < 0) return -1;      // x大于数组总和

    if (target == 0) return numsSize; // x等于数组总和，需要移除所有元素

    

    int left = 0;           // 窗口左边界

    int current_sum = 0;    // 当前窗口和

    int max_length = -1;    // 满足条件的最大子数组长度

    

    // 滑动窗口遍历

    for (int right = 0; right < numsSize; right++) {

        current_sum += nums[right];  // 扩展右边界

        

        // 收缩左边界直到窗口和小于等于target

        while (current_sum > target && left <= right) {

            current_sum -= nums[left];

            left++;

        }

        

        // 检查是否找到满足条件的子数组

        if (current_sum == target) {

            int current_length = right - left + 1;

            if (current_length > max_length) {

                max_length = current_length;

            }

        }

    }

    

    // 返回结果

    if (max_length == -1) {

        return -1;  // 没有找到满足条件的子数组

    } else {

        return numsSize - max_length;

    }

}

```

### 算法步骤详细解析

让我们逐步分析滑动窗口解法的执行过程：

```c

// 详细的步骤演示

void stepByStepDemo(int* nums, int numsSize, int x) {

    printf("\n=== 逐步演示 ===\n");

    printf("输入数组: ");

    printArray(nums, numsSize);

    printf(", x = %d\n", x);

    

    int total_sum = 0;

    for (int i = 0; i < numsSize; i++) {

        total_sum += nums[i];

    }

    printf("数组总和: %d\n", total_sum);

    

    int target = total_sum - x;

    printf("目标子数组和: %d\n", target);

    

    if (target < 0) {

        printf("x大于数组总和，无法实现\n");

        return;

    }

    

    int left = 0;

    int current_sum = 0;

    int max_length = -1;

    

    printf<"MX.0746.HK">("\n滑动窗口过程:\n");

    printf("右边界\t当前和\t左边界\t窗口状态\t操作\n");

    printf("------\t------\t------\t--------\t----\n");

    

    for (int right = 0; right < numsSize; right++) {

        current_sum += nums[right];

        printf("%d\t%d\t%d\t", right, current_sum, left);

        

        // 打印当前窗口

        printf("[");

        for (int i = left; i <= right; i++) {

            printf("%d", nums[i]);

            if (i < right) printf(",");

        }

        printf("]\t");

        

        // 收缩窗口

        while (current_sum > target && left <= right) {

            printf("收缩 ");

            current_sum -= nums[left];

            left++;

        }

        

        // 检查是否找到目标

        if (current_sum == target) {

            int current_length = right - left + 1;

            printf("找到目标! 长度=%d", current_length);

            if (current_length > max_length) {

                max_length = current_length;

                printf(" (新的最大值)");

            }

        } else {

            printf("继续");

        }

        printf("\n");

    }

    

    printf("\n结果: ");

    if (max_length == -1) {

        printf("-1 (无法实现)\n");

    } else {

        printf("%d (最小操作数 = %d - %d)\n", 

               numsSize - max_length, numsSize, max_length);

    }

}

```

### 完整测试用例

全面的测试用例验证算法正确性：

```c

// 测试用例函数

void testCases() {

    printf("=== LeetCode 1658 测试用例 ===\n\n");

    

    // 测试用例1：示例情况

    {

        int nums1[] = {1, 1, 4, 2, 3};

        int x1 = 5;

        printf("测试用例1: ");

        printArray(nums1, 5);

        printf(", x = %d\n", x1);

        int result1 = minOperations(nums1, 5, x1);

        printf("预期结果: 2, 实际结果: %d\n", result1);

        stepByStepDemo(nums1, 5, x1);

    }

    

    // 测试用例2：无法实现的情况

    {

        int nums2[] = {5, 6, 7, 8, 9};

        int x2 = 4;

        printf("\n测试用例2: ");

        printArray(nums2, 5);

        printf(", x = %d\n", x2);

        int result2 = minOperations(nums2, 5, x2);

        printf("预期结果: -1, 实际结果: %d\n", result2);

    }

    

    // 测试用例3：从单边移除

    {

        int nums3[] = {3, 2, 20, 1, 1, 3};

        int x3 = 10;

        printf("\n测试用例3: ");

        printArray(nums3, 6);

        printf(", x = %d\n", x3);

        int result3<"9B.8412.HK"> = minOperations(nums3, 6, x3);

        printf("预期结果: 5, 实际结果: %d\n", result3);

        stepByStepDemo(nums3, 6, x3);

    }

    

    // 测试用例4：需要从两边移除

    {

        int nums4[] = {1, 1, 1, 1, 1};

        int x4 = 5;

        printf("\n测试用例4: ");

        printArray(nums4, 5);

        printf(", x = %d\n", x4);

        int result4 = minOperations(nums4, 5, x4);

        printf("预期结果: 5, 实际结果: %d\n", result4);

    }

    

    // 测试用例5：空数组情况

    {

        int nums5[] = {};

        int x5 = 1;

        printf("\n测试用例5: 空数组, x = %d\n", x5);

        int result5 = minOperations(nums5, 0, x5);

        printf("预期结果: -1, 实际结果: %d\n", result5);

    }

    

    // 测试用例6：x等于0

    {

        int nums6[] = {1, 2, 3};

        int x6 = 0;

        printf("\n测试用例6: ");

        printArray(nums6, 3);

        printf(", x = %d\n", x6);

        int result6 = minOperations(nums6, 3, x6);

        printf("预期结果: 0, 实际结果: %d\n", result6);

    }

}

```

### 算法复杂度分析

```c

// 复杂度分析函数

void complexityAnalysis() {

    printf("\n=== 算法复杂度分析 ===\n");

    

    printf("时间复杂度: O(n)\n");

    printf("  - 计算数组总和: O(n)\n");

    printf("  - 滑动窗口遍历: O(n) - 每个元素最多被访问两次\n");

    printf("  - 总体: O(n)\n\n");

    

    printf("空间复杂度: O(1)\n");

    printf("  - 只使用了常数级别的额外空间\n");

    printf("  - 变量: total_sum, target, left, current_sum, max_length\n\n");

    

    printf("对比其他方法:\n");

    printf("1. 暴力解法: O(2^n) - 检查所有可能的移除组合\n");

    printf("2. 动态规划: O(n*x) - 可能超时且空间复杂度高\n");

    printf("3. 滑动窗口: O(n)   - 最优解\n");

}

```

### 边界情况处理

详细处理各种边界情况：

```c

// 边界情况处理函数

void handleEdgeCases() {

    printf("\n=== 边界情况处理 ===\n");

    

    // 情况1：x大于数组总和

    {

        int nums[] = {1, 2, 3};

        int x = 10;

        printf("情况1 - x大于数组总和: ");

        int result = minOperations(nums, 3, x);

        printf("结果: %d (正确应为-1)\n", result);

    }

    

    // 情况2：x等于数组总和

    {

        int nums[] = {1, 2, 3, 4};

        int x = 10;

        printf("情况2 - x等于数组总和: ");

        int result = minOperations(nums, 4, x);

        printf("结果: %d (正确应为4)\n", result);

    }

    

    // 情况3：空数组

    {

        int nums[] = {};

        int x = 5;

        printf("情况3 - 空数组: ");

        int result = minOperations(nums, 0, x);

        printf("结果: %d (正确应为-1)\n", result);

    }

    

    // 情况4：x等于0

    {

        int nums[] = {1, 2, 3};

        int x = 0;

        printf("情况4 - x等于0: ");

        int result = minOperations(nums, 3, x);

        printf("结果: %d (正确应为0)\n", result);

    }

    

    // 情况5：单个元素

    {

        int nums[] = {5};

        int x = 5;

        printf("情况5 - 单个元素且x等于该元素: ");

        int result = minOperations(nums, 1, x);

        printf("结果: %d (正确应为1)\n", result);

    }

}

```

### 滑动窗口技巧总结

```c

// 滑动窗口技巧总结

void slidingWindowTechniques<"2T.1853.HK">() {

    printf("\n=== 滑动窗口技巧总结 ===\n");

    

    printf("适用场景:\n");

    printf("1. 子数组/子字符串问题\n");

    printf("2. 需要找到满足某些条件的连续子序列\n");

    printf("3. 涉及数组和、乘积等累积操作的问题\n\n");

    

    printf("基本模板:\n");

    printf("int left = 0;\n");

    printf("for (int right = 0; right < n; right++) {\n");

    printf("    // 扩展右边界\n");

    printf("    // 更新状态变量\n");

    printf("    \n");

    printf("    while (/* 不满足条件 */) {\n");

    printf("        // 收缩左边界\n");

    printf("        // 更新状态变量\n");

    printf("    }\n");

    printf("    \n");

    printf("    // 检查是否找到解\n");

    printf("}\n\n");

    

    printf("本题的特殊转换:\n");

    printf("原问题: 移除两端元素和 = x\n");

    printf("转换后: 中间子数组和 = total - x\n");

    printf("最小操作数 = 总长度 - 最长子数组长度\n");

}

```

### 性能优化建议

```c

// 性能优化建议

void performanceOptimization() {

    printf("\n=== 性能优化建议 ===\n");

    

    printf("1. 提前终止检查:\n");

    printf("   if (target < 0) return -1;\n");

    printf("   if (target == 0) return numsSize;\n\n");

    

    printf("2. 使用局部变量:\n");

    printf("   将频繁访问的数组成员存储在局部变量中\n\n");

    

    printf("3. 避免不必要的计算:\n");

    printf("   只在必要时更新最大值\n\n");

    

    printf("4. 边界条件优先处理:\n");

    printf("   在主要逻辑之前处理明显的边界情况\n");

}

// 优化版本实现

int minOperationsOptimized(int* nums, int numsSize, int x) {

    // 快速边界检查

    if (numsSize == 0)<"m.6370.HK"> return x == 0 ? 0 : -1;

    

    // 计算总和

    int total_sum = 0;

    for (int i = 0; i < numsSize; i++) {

        total_sum += nums[i];

    }

    

    int target = total_sum - x;

    

    // 快速边界返回

    if (target < 0) return -1;

    if (target == 0) return numsSize;

    

    int left = 0;

    int current_sum = 0;

    int max_length = -1;

    

    for (int right = 0; right < numsSize; right++) {

        current_sum += nums[right];

        

        // 快速收缩

        while (current_sum > target && left <= right) {

            current_sum -= nums[left++];

        }

        

        if (current_sum == target) {

            int current_length = right - left + 1;

            if (current_length > max_length) {

                max_length = current_length;

            }

        }

    }

    

    return max_length == -1 ? -1 : numsSize - max_length;

}

```

### 完整可运行程序

```c

// 主函数 - 整合所有功能

int main() {

    printf("LeetCode 1658 - 将 x 减到 0 的最小操作数\n");

    printf("=========================================\n\n");

    

    // 问题分析

    problemAnalysis();

    

    // 测试用例

    testCases();

    

    // 算法分析

    complexityAnalysis();

    

    // 边界情况

    handleEdgeCases();

    

    // 技巧总结

    slidingWindowTechniques();

    

    // 性能优化

    performanceOptimization();

    

    printf("\n=== 程序结束 ===\n");

    return 0;

}

```

### 总结

LeetCode 1658题的滑动窗口解法展示了算法思维的精妙之处：

1. **问题转换**：将两端移除问题转换为寻找中间子数组问题

2. **滑动窗口**：高效找到满足条件的最大子数组

3. **数学关系**：`操作数 = 总长度 - 子数组长度`

4. **边界处理**：全面考虑各种特殊情况

这种方法的时间复杂度为O(n)，空间复杂度为O(1)，是解决该问题的最优方案。掌握这种问题转换思维和滑动窗口技巧，对于解决类似的数组优化问题具有重要意义。