滑动窗口

滑动窗口

滑动窗口（Sliding Window）是一种常用的算法技巧，通常用于解决涉及子数组或子序列的最优化问题。它的核心思想是利用两个指针（窗口的左右边界），通过动态调整窗口的大小来遍历数据结构，从而有效地解决问题。

长度最小的子数组（leetcode.209）

https://leetcode.cn/problems/minimum-size-subarray-sum/description/?envType=problem-list-v2&envId=sliding-window

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 左指针 l, 右指针 r, 当前窗口的和 sum, 最终答案 ans 初始化为 INT_MAX
        int l = 0, r = 0, sum = 0, ans = INT_MAX;
    
        for (r = 0; r < nums.size(); r++) {
            sum += nums[r];  

            // 如果当前窗口的和 sum 大于或等于 target，尝试缩小窗口
            while (sum - nums[l] >= target) {
                sum -= nums[l++];  // 左指针向右滑动，减少窗口和 sum
            }

            // 如果当前窗口的和 sum 大于或等于 target，更新答案
            if (sum >= target) {
                ans = min(ans, r - l + 1);  // 更新最小窗口长度
            }
        }

        // 如果没有找到符合条件的子数组，返回 0，否则返回最小长度
        return ans == INT_MAX ? 0 : ans;
    }
};

无重复字符的最长字串（leetcode.3）

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=problem-list-v2&envId=sliding-window