滑动窗口算法详解：经典例题解析

滑动窗口算法详解

(一) 长度最小的子数组

题目链接： https://leetcode.cn/problems/minimum-size-subarray-sum/

1.1 题目分析

这道题要求我们在数组中找一个区间，这个区间的元素的和等于题目给出的 target，如果找不到则返回 0。

1.2 算法原理

解法一：暴力遍历出所有的区间，然后找到最小区间。如果我们按照这种方法就需要两个循环才能解决问题，时间复杂度为 O(n^2)，效率非常低。

解法二：利用单调性，使用同向双指针（同向双指针就是我们的滑动窗口）。

1.3 代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0, len = INT_MAX;
        int n = nums.size();
        while (right < n) {
            sum += nums[right]; // 入窗口
            while (sum >= target) { // 判断
                len = min(len, right - left + 1); // 更新 len
                sum -= nums[left++]; // 划出窗口
            }
            right++; // 再入窗口
        }
        return len == INT_MAX ? 0 : len;
    }
};

(二) 无重复字符的最长子串

题目链接： https://leetcode.cn/problems/longest-substring-without-repeating-characters/

2.1 题目分析

题目的意思就是让我们找一个区间，在这个区间里的元素没有重复，返回区间的大小。

2.2 算法原理

解法一：暴力枚举 + 哈希表（去重）。

解法二：根据规律，使用滑动窗口来解决问题。