滑动窗口

2022年11月8日 43点热度 0人点赞 0条评论

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. 无重复字符的最长子串
    1. 水果成篮
  • 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 个节点
  • 删除有序数组中的重复项
  • 盛最多水的容器
  • 接雨水

rainbow

没什么大用的码农; 贴图怪; bug制造者; 只会电脑开关机的开发;

文章评论