题目描述
给定一个含有 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
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
一、思路
两种思路:直接暴力 和 滑动窗口(另一种形式的双指针)
暴力法:
两个for循环,可以把i 和 j 想象成头指针和尾指针,思路是通过定位头指针来依次遍历尾指针,实时更新长度的变化和长度和的变化,然后跟目标值进行比较,这样的话时间复杂度是O(n^2),因为力扣上又更新了新的数据,所以暴力法超时。
双指针变形:滑动窗口
滑动窗口的理解:不同于暴力解法那样定位头指针移动尾指针,滑动窗口的精髓在于通过定位尾部指针来移动头部指针。利用一个for循环解决了两个for循环问题。同时也实时更新和记录最小区间的长度变化。
本题中的滑动窗口在使用了一个for循环的同时,又添了一个while循环来用于判断,有的同学可能使用了if语句来进行条件判断,为什么不用if语句来进行判断呢?
这里使用while循环 因为如果出现类似于 2 2 2 2 50 target=50 此时首次出现符合条件 首指针在索引为0,尾指针到了末尾 ,此时就不能使用if()来判断了 ,需要多次缩小滑动窗口的长度
二、参考代码
暴力法
class Solution { public int minSubArrayLen(int target, int[] nums) { // 暴力法:超时 时间复杂度O(n^2) int sum = Integer.MAX_VALUE; int count = 0; int length = 0; for(int i =0;i<nums.length;i++){ count = 0; for(int j=i;j<nums.length;j++){ count+=nums[j]; if(count>=target){ length = j-i+1; sum=length<sum?length:sum; break; } } } return sum == Integer.MAX_VALUE?0:sum; } }
双指针–滑动窗口:
class Solution { // 双指针的另一种应用 滑动窗口 // 暴力法可以想想成两个指针 通过定位头指针位置,然后依次遍历尾指针寻找最小的值 // 滑动窗口的思路在于:通过定位尾指针的位置,然后依次移动头指针的位置来进行判断 // 利用一个for循环解决了两个for循环的问题 public int minSubArrayLen(int target, int[] nums) { // 定义变量记录长度 int length=0; // 定义变量记录长度和; int num = 0; // 定义头指针位置 int index = 0; // 定义用来记录最小长度和 int result = Integer.MAX_VALUE; // 定义尾指针的位置; for(int j =0;j<nums.length;j++){ num+=nums[j]; // 这里使用while循环 因为如果出现类似于 2 2 2 2 50 target=50 此时首次出现符合条件 首指针在索引为0,尾指针到了末尾 ,此时就不能使用if()来判断了 ,需要多次缩小滑动窗口的长度 while(num>=target){ length = j-index+1; // 移动头指针,来缩小滑动窗口长度 num -= nums[index++]; result = result<length?result:length; } } return result == Integer.MAX_VALUE ? 0:result; } }