滑动窗口

KMP 算法是应用了滑动窗口最典型的例子, 但此片文章不以 KMP 算法来做讲解例子, 因为这个算法里面已经容纳了很多前人的处理与思想, 难懂的同时可能自带劝退属性. 数组是一种基本的数据结构, 会写代码的人不会数组操作都不敢出门见人, 但是很多基于数据的操作会浪费大量的时间, 滑动窗口就是为了帮助我们提升效率的一种算法.

滑动窗口模板

// int n = 数组长度;
for(int l = 0, r = 0; r < n; ++r) {
    // 右边滑入窗口;
    // while(不符合条件)
        // 左边滑出窗口;
    if(/* 满足条件 */)
        // 记录
}

209. 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLen = INT_MAX;
        int n = nums.size();
        int sum = 0;
        for(int l = 0, r = 0; r < n; ++r) {
            sum += nums[r];
            while(sum - nums[l] >= target)
                sum -= nums[l++];
            if(sum >= target)
                minLen = min(minLen, r - l + 1);
        }
        return minLen == INT_MAX ? 0 : minLen;
    }
};

相关题目

• 【Python, JavaScript】滑动窗口 (3. 无重复字符的最长子串)
• 最小覆盖子串
• 长度最小的子数组
• 【Python】滑动窗口 (438. 找到字符串中所有字母异位词)
• 【904. 水果成篮】(Python3)
• 【930. 和相同的二元子数组】(Java, Python)
• 【992. K 个不同整数的子数组】滑动窗口 (Python)
• 【1004. 最大连续 1 的个数 III】滑动窗口 (Python3)
• 【1234. 替换子串得到平衡字符串】[Java/C++/Python] Sliding Window
• 【1248. 统计「优美子数组」】滑动窗口 (Python)
• 最小覆盖子串 (LeetCode76)
• 字符串排列 (LeetCode567)
• 统计字母异位词 (LeetCode438)
• 最长无重复子串 (LeetCode3)
• 面试题 16.17. 连续数列
• 给定一个整数数组, 找出总和最大的连续数列, 并返回总和.
• 最大子序和
• LeetCode209. 长度最小的子数组
• LeetCode 3. 无重复字符的最长子串
• 904. 水果成篮
• Find the longest substring of a given string containing k distinct characters
• Find all substrings of a string that are permutation of a given string
• Longest substring of given string containing distinct characters
• Find maximum length sequence of continuous ones (Using Sliding Window)
• Find the maximum sequence of continuous 1's that can be formed by replacing at-most k zeroes by ones
• Find minimum sum subarray of given size k
• Find subarray having given sum in given array of integers
• Find the length of the smallest subarray whose sum of elements is greater than the given number
• Find the count of distinct elements in every sub-array of size k
• Print all sub-arrays of an array having distinct elements
• Count the distinct absolute values in the sorted array
• Find duplicates within given range k in an array
• 两数之和
• 三数之和
• 四数之和
• 无重复字符的最长子串
• 环形链表
• 判断链表中点
• 链表中倒数第 k 个节点
• 删除有序数组中的重复项
• 盛最多水的容器
• 接雨水