【C++】优选算法必修篇之滑动窗口实战：长度最小的子数组 & 无重复字符的最长子串

我不是呆头

发布于 2025-12-20 14:32:18

2030

应用场景

我们可以把滑动窗口想象成一台在数据序列上“巡逻的摄像机”。这台摄像机拍摄的，总是一段连续的画面（即一个“子数组”或“子串”）。我们的任务，就是通过移动这台摄像机，找到满足特定要求的那段最精彩、或是最短的画面。

它的核心工作方式非常巧妙：通常有两个指针，一左一右，共同框定了摄像机的取景范围。右指针像是一个“开拓者”，负责向前探索，不断将新的元素纳入取景范围；而左指针则像是一个“优化师”，在条件满足时，负责从后面收紧范围，剔除不必要的元素，以寻找更优的解答。这一前一后、一扩一缩的配合，使得它不用重复检查所有可能的画面，就能高效地找到目标。

当我们接到的问题是关于寻找“最长的”符合条件的一段时，滑动窗口就派上了大用场。比如，要在一个字符串里找到不包含重复字母的最长片段。这时，我们的策略是：只要当前画面里没有重复，右指针就大胆地向前扩展，努力让画面变得更长。一旦发现某个新元素造成了重复（比如出现了两个相同的字母），左指针就立刻开始工作，从左向右收缩画面，直到把那个惹事的重复元素排除出去为止。在整个过程中，我们记录下所获得的最大窗口尺寸，那就是我们想要的“最长片段”。
与之相对，当我们的目标是寻找“最短的”符合条件的一段时，比如在一个都是正数的数组中，找到和大于等于某个目标值的最短子数组，策略就变了。这时，右指针依然向前探索，累加元素的和。一旦发现当前窗口内的总和达到了目标，我们就知道这是一个候选解。紧接着，左指针就开始行动，尝试从左端移除元素，目的是在仍然满足总和大于等于目标值的前提下，看看这个窗口能缩短到多小。我们记录下这个过程中的最小窗口尺寸，最终找到的就是那个“最短片段”。
在实现这个算法的过程中，我们常常需要一个得力的“助手”——哈希表（或叫字典）。 尤其是在处理涉及元素出现次数或唯一性的问题时。比如，在找“最长无重复子串”时，我们可以用哈希表来快速记录每个字符最后一次出现的位置。当右指针遇到一个重复字符时，左指针不用一步一步地挪动，而是可以直接“跳跃”到哈希表记录的那个重复字符上一次出现位置的下一个位置。这个“跳跃”极大地提高了效率，是滑动窗口算法能保持高性能的关键技巧之一。

总而言之，滑动窗口的精髓在于，它通过两个指针的动态移动，聪明地维护着一个满足或试图满足条件的连续区间。它将很多看似复杂的问题时间复杂度从O(n²)降低到了高效的O(n)，是处理连续子区间、子串问题的首选利器。

1. 长度最小的子数组

1.1 题目链接

题目链接直达请点击<----------

1.2 题目描述

1.3 题目示例

1.4 算法思路

初始化左右指针指向数组第一个元素，然后让右指针右滑，每次指向的数据就累加，让sum直到累加的和大于等于traget。（并初始化一个len为INT_MAX ）

在这个过程中sum += nums[right++]就是在不断进窗口

记录下当前的长度，并更新最小长度。接下来开始left指针++，并且sum -= nums[right++],直到不满足sum大于等于traget这个结果。

在这个过程中sum -= nums[left++]就是在不断出窗口

我们就不断循环这个过程，在for里面执行进入窗口的操作，之后套一个while，当满足sum>=traget的时候执行更新结果和出窗口的操作，最后返回最短的结果。

1.5 核心代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0,right = 0;
        int n = nums.size();
        int len = INT_MAX;
        int sum = 0;

        for(right = 0;right < n;right++)
        {
            
            sum += nums[right];//进入窗口
            while(sum >= target)//判断
            {
                len = min(len,right-left+1);//更新结果
                sum -= nums[left++];//出窗口，减去左边left的值，因为右边固定，左边++，sum总会单调递减，直到sum<traget时，左边固定，右边++直到下一次循环
            }
            
        }
        return len == INT_MAX ? 0 : len;
    }
};

1.6 示例测试（总代码）

//最短子数组长度 & 无重复字符最长子串
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int n = nums.size();
        int len = INT_MAX;
        int sum = 0;

        for (right = 0; right < n; right++)
        {

            sum += nums[right];//进入窗口
            while (sum >= target)//判断
            {
                len = min(len, right - left + 1);//更新结果
                sum -= nums[left++];//出窗口，减去左边left的值，因为右边固定，左边++，sum总会单调递减，直到sum<traget时，左边固定，右边++直到下一次循环
            }

        }
        return len == INT_MAX ? 0 : len;
    }
};

int main()
{
    vector<int> nums1 = { 2,3,1,2,4,3 };
    int target1 = 7;
    int result = Solution().minSubArrayLen(target1, nums1);

    cout << "最短子数组长度: " << result << endl;
}

2. 无重复字符的最长子串

2.1 题目链接

题目链接直达请点击<----------

2.2 题目描述

2.3 题目示例

2.4 算法思路

因为我们需要记录每个字符出现的次数：所以我们定义一个大小为128的整数数组hash作为哈希表，利用ASCII编码，将字符映射到数组下标（0-127）覆盖所有标准ASCII字符。

这样数组值记录对应字符在当前窗口内出现的次数

然后我们采用滑动窗口，用left标记当前无重复子串的起始位置（初始化为0），right用来探索新字符（初始化为0），扩展窗口右边界。

我们使用right逐个遍历字符串中字符，每遇到一个新字符，在哈希表中对应的位置计数加1（这里是进窗口），并更新它的最大长度（right-left+1）。

这里如上图，我们到一个重复的a，就需要将这个字符在哈希中的次数减掉一次然后left指针右移（这就是出窗口），然后更新长度
我们就不断循环这个过程，在for里面执行进入窗口的操作，之后套一个while，当满足hash[s[right]] > 1的时候出窗口的操作，然后再while循环外面执行更新结果和最后返回最短的结果。

2.5 核心代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};
        int left = 0,right = 0;
        int n = s.size();
        int ret = 0;
        for(right = 0;right < n; right++)
        {
            hash[s[right]]++;//进窗口,ascall编码表，记录每个字符出现的次数
            while(hash[s[right]] > 1)//判断
            {
                hash[s[left]]--;//出窗口，将模拟哈希中的字符次数--
                left++;//更新下标，缩小窗口
            }
            ret = max(ret,right - left + 1);//更新结果
        }
        return ret;
    }
};

2.6 示例测试（总代码）

#include<iostream>
#include<string>
using namespace std;


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 };
        int left = 0, right = 0;
        int n = s.size();
        int ret = 0;
        for (right = 0; right < n; right++)
        {
            hash[s[right]]++;//进窗口,ascall编码表，记录每个字符出现的次数
            while (hash[s[right]] > 1)//判断
            {
                hash[s[left]]--;//出窗口，将模拟哈希中的字符次数--
                left++;//更新下标，缩小窗口
            }
            ret = max(ret, right - left + 1);//更新结果
        }
        return ret;
    }
};
int main()
{
    string s1 = "abcabcbb";

    int result = Solution().lengthOfLongestSubstring(s1);
    cout << "无重复字符的最长子串长度: " << result << endl;

    return 0;
}