Leetcode经典题20--长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入输出示例

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解决方案

方式一：滑动窗口

算法思想

定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[start] 到 nums[end] 的元素和）。

初始状态下，start 和 end 都指向下标 0，sum 的值为 0。

每一轮迭代，将 nums[end] 加到 sum，如果 sum≥s，则更新子数组的最小长度（此时子数组的长度是 end−start+1），然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum

实现代码

class Solution {public int minSubArrayLen(int target, int[] nums) {int n=nums.length;if(n==0){return 0;}int ans=Integer.MAX_VALUE;int start=0,end=0;//窗口的左边界和右边界int sum=0;//窗口的元素和while(end<n){//向右滑动sum+=nums[end];//当窗口内的元素和大于等于目标值，缩小窗口while(sum>=target){ans=Math.min(ans,end-start+1);sum-=nums[start];start++;}//否则扩大窗口end++;}//考虑达不到目标值的情况return ans==Integer.MAX_VALUE?0:ans;}
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。

空间复杂度：O(1)。