朝文分享（58）：畅游算法之海(四）——滑动窗口

摘要：Share interest, spread happiness, increase knowledge, and leave beautiful.

分享兴趣，传播快乐，增长见闻，留下美好！

亲爱的您，这里是LearningYard新学苑。

今天小编为大家带来“畅游算法之海(四）——滑动窗口”，欢迎您的访问。

Share interest, spread happiness, increase knowledge, and leave beautiful.

Dear, this is the LearingYard Academy!

Today, Swim the sea of algorithms (4) - Sliding window ，welcome to visit!

一、简介

1. Introduction

本次的问题是长度最小的子数组。给定一个含n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回0。该问题对应力扣的209。

The problem this time is the smallest subarray. Given an array of n positive integers and a positive integer target. Find the smallest subarray in the array whose sum is greater than or equal to the target and return its length. If no matching subarray exists, return 0. The problem is on the stress buckle of 209.

二、原理

2. Principle

这个问题如何解决？首先想到的是双层循环的暴力实现。一层循环遍历数组，另一层循环不断求和，更新长度。这种方法运行过程繁琐，时间久，效率低。而本次要分享的方法是窗口滑动。窗口滑动也是用到双指针。根据上述问题，进行窗口滑动过程的模拟。

How can this problem be solved? The first thing that comes to mind is the realization of violence in a two-tier cycle. One layer loops through groups of numbers, and the other layer loops continuously sum and update the length. The operation process of this method is complicated, long time and low efficiency. The method to share this time is window sliding. Window sliding also uses double Pointers. According to the above problems, the window sliding process is simulated.

窗口左右起始点都为0，右下标遍历整个数组，左下标根据窗口之和进行滑动，使得窗口之和小于target。

The left and right start points of the window are 0, the right subscript traverses the entire array, and the left subscript slides according to the sum of Windows, so that the sum of Windows is less than the target.

一旦窗口之和大于等于target，就要滑动窗口左下标。直到窗口之和小于target，停止滑动，右下标继续遍历。重复操作，直至右下标遍历结束。

Once the sum of Windows is greater than or equal to target, slide the left subscript of the window. Until the sum of Windows is less than target, the sliding stops and the right subscript continues traversing. Repeat until the right subscript traversal is complete.

遍历结束之后，返回result。

At the end of the loop, result is returned.

三、实现

3. Implementation

窗口滑动仅通过一层循环就能解决问题。相比暴力算法，运行时间更短，运行更快，效率更高。其核心在于两个指针不是独立的，左下标根据右下标不断滑动，更新整个窗口。根据上述过程，编写代码，解决问题。

Window sliding solves the problem with just one layer of loops. Compared with the brute force algorithm, the running time is shorter, the operation is faster, and the efficiency is higher. The core is that the two Pointers are not independent, and the left subscript constantly slides according to the right subscript, updating the entire window. According to the above process, write code and solve problems.