文章目录
- 1. 题目链接
- 2. 题目大意
- 3. 示例
- 4. 解题思路
- 5. 参考代码
1. 题目链接
209. 长度最小的子数组 - 力扣(LeetCode)
2. 题目大意
描述:给定一个只包含正整数的数组 nums 和一个正整数 target。
要求:找出数组中满足和大于等于 target 的长度最小的「连续子数组」,
并返回其长度。如果不存在符合条件的子数组,返回 0。
说明:
- 1≤target≤109。
- 1≤nums.length≤105。
- 1≤nums[i]≤105。
3. 示例
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
输入:target = 4, nums = [1,4,4]
输出:1
4. 解题思路
最直接的做法是暴力枚举,时间复杂度为 O(n2)。但是我们可以利用滑动窗口的方法,在时间复杂度为 O(n) 的范围内解决问题。
用滑动窗口来记录连续子数组的和,设定两个指针:left、right,分别指向滑动窗口的左右边界,保证窗口中的和刚好大于等于 target。
- 一开始,left、right 都指向 0。
- 向右移动 right,将最右侧元素加入当前窗口和 window‾sum 中。
- 如果 window‾sum≥target,则不断右移 left,缩小滑动窗口长度,并更新窗口和的最小值,直到 window‾sum<target。
- 然后继续右移 right,直到 right≥len(nums) 结束。
- 输出窗口和的最小值作为答案。
5. 参考代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int size = nums.length;int ans = size + 1; // 初始化为比数组长度大1的值,方便后续判断int left = 0;int right = 0;int windowSum = 0;while (right < size) {windowSum += nums[right];// 当窗口内的和大于等于目标值时,尝试缩小窗口while (windowSum >= target) {ans = Math.min(ans, right - left + 1);windowSum -= nums[left];left++;}right++;}return ans == size + 1 ? 0 : ans;}
}