滑动窗口算法深度解析：LeetCode 经典例题实战

通过五个 LeetCode 经典例题（最小操作数、水果成篮、字母异位词、串联所有单词的子串、最小覆盖子串），详细讲解了滑动窗口算法的核心思想与实现技巧。内容涵盖暴力解法优化、双指针移动策略、哈希表计数维护以及边界条件处理，提供完整的 C++ 代码示例与复杂度分析，帮助读者掌握滑动窗口在字符串和数组问题中的应用。

漫步发布于 2026/3/29更新于 2026/9/977 浏览

12. 将 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，最优的操作次数是 2 次。对于示例 2，不论是从左边还是右边进行删除操作，x 永远不可能到 0，所以返回 -1。

我们将问题进行转换：原来要求的是从最左边或者最右边进行删除元素，直到 x 变成 0。我们可以将问题区域划分，左边的区域是 a，右边的区域是 b，a 区域和 b 区域里面的数值加起来等于 x。那么中间剩下的就是我们整个数组的值减去 x。题目让我们求出最小的操作次数，也就是说 a+b 最短的情况，换种思路，就是中间区域最长的情况，即 sum-x。我们只要求出整个数组中和为 sum-x 的区域的最长值就行了。

找出最长的子数组的长度，子数组的所有元素的和正好等于 sum-x。

做这种题我们可以想对立面。我们可以先想想暴力解法：设置两个指针，左和右，一开始指向起点，让右指针进行移动操作，直到两个指针的区域间的值大于等于 sum-x，我们就更新下我们的操作次数，然后移动左指针继续进行更新的操作。

当左指针往右边移动了，右指针就没有必要往左边进行移动了，因为左指针向右移动过后，区间中的元素大小更小了，右指针只能往右移动。

在这个暴力解法的基础上进行优化：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int a : nums) {
            sum += a;
        }
        int target = sum - x;
        // 细节问题，target 的值不能小于 0
        if (target < 0) return -1;
        int ret = -1;
        for (int left = , right = , tmp = ; right < nums.(); right++) {
            
            tmp += nums[right]; 
             (tmp > target) { 
                tmp -= nums[left];
                left++; 
            }
             (tmp == target) { 
                
                ret = (ret, right - left + );
            }
        }
         (ret == )  ret; 
          nums.() - ret; 
    }
};

12. 将 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，最优的操作次数是 2 次。对于示例 2，不论是从左边还是右边进行删除操作，x 永远不可能到 0，所以返回 -1。

找出最长的子数组的长度，子数组的所有元素的和正好等于 sum-x。

当左指针往右边移动了，右指针就没有必要往左边进行移动了，因为左指针向右移动过后，区间中的元素大小更小了，右指针只能往右移动。

在这个暴力解法的基础上进行优化：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int a : nums) {
            sum += a;
        }
        int target = sum - x;
        // 细节问题，target 的值不能小于 0
        if (target < 0) return -1;
        int ret = -1;
        for (int left = , right = , tmp = ; right < nums.(); right++) {
            
            tmp += nums[right]; 
             (tmp > target) { 
                tmp -= nums[left];
                left++; 
            }
             (tmp == target) { 
                
                ret = (ret, right - left + );
            }
        }
         (ret == )  ret; 
          nums.() - ret; 
    }
};

class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> ret; // 创建一个哈希表并且将单词在 word 中出现的次数进行记录 unordered_map<string, int> hash1; // 保存 words 里面所有的单词的频次 for (auto& w : words) hash1[w]++; // 记录 words 里面所有的单词出现的频次 // 计算单词的长度 int len = words[0].size(), m = words.size(); // 多少个单词 // 我们这里的滑动窗口是需要执行 len 次的 for (int i = 0; i < len; i++) { // 执行 len 次滑动窗口 unordered_map<string, int> hash2; // 维护滑动窗口内单词的频次 // 因为我们 right 在移动到对应的位置后，我们需要将 right+len 个字符放到滑动窗口里面去 for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) { // count 就是有效字符串的个数了 // 进窗口 + 维护 count string in = s.substr(right, len); // 直接获取 right 后面 len 个字符，那么 in 就是一个字符串了 hash2[in]++; // 我们将 in 这个字符出现的频次进行更新 if (hash1.count(in) && hash2[in] <= hash1[in]) count++; // 如果我们 hash2 这个哈希中当前字符串出现的频次小于 hash1 的话，说明是有效单词，如果我们哈希 2 里面这个字符串出现次数大于哈希 1 的话，那么这个肯定是一个无效的单词，因为 hash1 中都没有进行记录 // 判断 if (right - left + 1 > len * m) { // 如果我们当前左右指针的范围大于我们要找的子串的长度的话，那么我们就进行出窗口操作 // 出窗口，维护 count string out = s.substr(left, len); // 我们将 left 后面三个单词的范围的这个字符串拿出来 if (hash1.count(out) && hash2[out] <= hash1[out]) count--; // 有效单词减一 hash2[out]--; // 出完窗口之后，我们的 left 需要向后移动 left += len; } // 更新结果 if (count == m) ret.push_back(left); // 将我们 } } // 当整个循环结束之后，我们 ret 中存储的就是结果了 return ret; } };

class Solution { public: string minWindow(string s, string t) { int hash1[128] = {0}; // 统计 t 字符串中每一个字符出现的频次 int kinds = 0; // 统计有效字符有多少种 for (auto ch : t) { // 如何判断我们当前的有效字符种类是否增加了呢？ // 如果在进窗口前这个字符数量为 0 的话，并且是有效字符的话，那么我们的种类就多了一种了 if (hash1[ch] == 0) kinds++; // 有效字符的种类加一 hash1[ch]++; } // 出了循环我们就统计到了我们字符的种类数量 int hash2[128] = {0}; // 统计窗口内每个字符的频次 int minlen = INT_MAX, begin = -1; for (int left = 0, right = 0, count = 0; right < s.size(); right++) { char in = s[right]; // 获取我们这个字符的信息 hash2[in]++; // 给这个字符的次数++ // 判断我们加入的字符是否是有效字符 // 进窗口 + 维护 count 变量 if (hash2[in] == hash1[in]) count++; // 说明我们加入了一个有效的字符 // 判断条件 while (count == kinds) { // 更新结果 if (right - left + 1 < minlen) { // 说明此时我们需要更新结果了 // 计算最小的子串的长度 minlen = right - left + 1; // 开始的指针指向我们的 left begin = left; } // 出窗口 char out = s[left]; // 记录当前出窗口的单词 left++; // 左指针往右边走 // 维护 count if (hash2[out] == hash1[out]) count--; // 说明我们当前的字符是有效字符 hash2[out]--; // 将当前出窗口的字符进行--操作 } } if (begin == -1) return ""; // 如果我们开始的指针没有变的话，那么我们就直接返回空就行了 else return s.substr(begin, minlen); // 如果变了的话，我们 begin 后面 minlen 个范围的字符串获取然后返回就行了 } };

滑动窗口算法深度解析：LeetCode 经典例题实战

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

滑动窗口算法深度解析：LeetCode 经典例题实战

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

更多推荐文章

相关免费在线工具

13. 水果成篮

14. 找到字符串中所有字母异位词

15. 串联所有单词的子串

16. 最小覆盖子串

更多推荐文章

相关免费在线工具