LeetCode算法题——长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
题解
解法一：暴力解法
思路： 该题可使用暴力解法求解，用双层for循环，计算每一种可能情况下的子数组长度并求得最小值。暴力解法在力扣上由于超时无法通过测试，因此不采用次方法。
解法二：滑动窗口解法
思路： 利用滑动窗口思路进行解决，定义起始指针和终止指针，这里需要考虑的问题就是两个指针什么时候移动。终止指针：从头到尾逐步移动，起始指针：终止指针每向后移动一步，计算窗口内的元素总值sum，到sum大于等于目标值，则起始指针向后移动，直到窗口内元素总值小于目标值则停止移动，并记录下当前子数组的长度。但终止指针从头到尾遍历完成后所得到的最小滑动窗口长度即为所求值。
总结
- 滑动窗口机制是一种用于高效处理数组、字符串相关算法的策略。它借助两个指针界定出一个动态的“窗口”，起始时指针多位于序列开头。运算中，右指针右移来扩展窗口，不断纳入新元素，累积所需信息，像统计数量、求和；一旦窗口满足既定条件，左指针右移，收缩窗口，剔除多余元素，同时更新满足要求的结果。借由这样有节奏的窗口滑动，只需线性遍历一次数据序列，就将原本可能O (n²)的时间复杂度降为O(n)，还常维持O(1)的空间复杂度，极为适配求和、子串匹配、频次统计这类问题。