数组 长度最小的组数组 滑动窗口 Leetcode209
2024-03-07 本文已影响0人
宗驴
需求：
给定一个含有n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组[4,3]是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]输出：1
思路：
拿到这个题目理解不是很清晰，理解为找出最小的数组集合并返回，这个过程就要记录遍历过程中的所有集合，这就有很多中可能性。再对已有几何对比长度大小，思考到这基本就大脑宕机了，无法进行下去了。实际是找出长度即可，重点不在数组内容。
暴力方式：
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。
滑动窗口：
滑动窗口概念了类似互联网登录验证将一个图像滑动到一定位置。不同的是这个窗口的宽度是根据计算变化的，也就是我们要求的这个自己长度。
首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。
源码实现
测试结果
