LeetCode 滑动窗口算法详解：核心思路与实战案例

无重复字符的最长子串

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

• 输入：s = "abcabcbb"
• 输出：3
• 解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

实现思路

这道题同样适用滑动窗口，但约束条件变为'窗口内不能有重复字符'。我们需要借助哈希表（或数组）记录字符出现的次数。

当右指针移入新字符时，检查该字符是否已存在。如果存在（计数大于 1），则移动左指针直到移除重复字符为止。在此过程中不断更新最大长度。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int n = s.size();
        int len = -1;
        for (int i = 0, j = 0; j < n;) {
            hash[s[j]] += 1;
            while (hash[s[j]] > 1) {
                hash[s[i++]]--;
            }
            len = max(len, j - i + 1);
            j++;
        }
        return len == -1 ? 0 : len;
    }
};

最大连续 1 的个数 III

题目描述

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0，则返回执行操作后数组中连续 1 的最大个数。

示例：

• 输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
• 输出：6
• 解释：翻转两个 0 后，最长的连续 1 的子数组长度为 6。

实现思路

这个问题可以转化为求一个最长区间，使得区间内 0 的个数不超过 k 个。我们依然使用双指针维护窗口。

右指针遍历时统计 0 的数量，一旦超过 k，就移动左指针直到 0 的数量回到 k 以内。每次合法状态下更新最大长度。

代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt = 0;
        int ret = -1;
        for (int i = 0, j = 0; j < n; j++) {
            if (nums[j] == 0) {
                cnt++;
            }
            while (cnt > k) {
                if (nums[i++] == 0) {
                    cnt--;
                }
            }
            ret = max(ret, j - i + 1);
        }
        return ret == -1 ? 0 : ret;
    }
};

将 x 减到 0 的最小操作数

题目描述

给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。如果可以将 x 恰好减到 0，返回 最小操作数；否则，返回 -1。

示例：

• 输入：nums = [1,1,4,2,3], x = 5
• 输出：2
• 解释：最佳解决方案是移除后两个元素，将 x 减到 0。

实现思路

这道题具有迷惑性，直接模拟移除过程较难。换个角度思考：移除两端元素等价于保留中间的一段连续子数组，且这段子数组的和等于 总和 - x。

因此，问题转化为求和为 target = sum(nums) - x 的最长子数组。如果找到这样的子数组，原问题的答案就是 总长度 - 子数组长度。若 target < 0 或无法找到，则返回 -1。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int k = 0;
        for (auto s : nums) {
            k += s;
        }
        k -= x;
        if (k < 0) return -1;
        
        int len = -1;
        int sum = 0;
        for (int i = 0, j = 0; j < n; j++) {
            sum += nums[j]; // 进窗口
            while (sum > k) {
                sum -= nums[i++]; // 出窗口
            }
            if (sum == k) {
                len = max(len, j - i + 1);
            }
        }
        return len == -1 ? -1 : n - len;
    }
};