力扣209：长度最小的数组

本文主要是介绍力扣209：长度最小的数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个含有 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

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

方法一：暴力（会超出时间限制）

思想，利用两个for循环，从前往后遍历数组，找出该数组中满足其总和大于等于 target 的长度最小的 子数组。

代码：

int minSubArrayLen(int s, int* nums, int numsSize) {if (numsSize == 0) {return 0;}int ans = INT_MAX;for (int i = 0; i < numsSize; i++) {int sum = 0;for (int j = i; j < numsSize; j++) {sum += nums[j];if (sum >= s) {ans = fmin(ans, j - i + 1);break;}}}return ans == INT_MAX ? 0 : ans;
}

时间复杂度O（n^2）；空间复杂度O（1）

方法二：滑动窗口

思想：定义两个指针i和j，i表示起始位置，j表示结束位置。开始时，将最小距离设置成INT_MAX。开始时，i不变，从移动前往后移动j遍历数组，计算总和sum，当sum大于等于target时，将result更新为最小距离。并将sum减去nums[i]，将i往后面遍历。最后去result的最小值。

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

开始i=0，j=0，nums[i]=num[j]=2；移动j，进行遍历。直到sum=[2+3+1+2]=8>target时，result=j-i+1=4；sum=[3+1+2]=6；i=1；继续往后遍历。

i=1，j=3,移动j，直到sum=[3+1+2+4]=10时，result=4，sum=[1+2+4]=7；i=2；继续往后遍历。

此时sum=7，result=j-i+1=3；sum=[2+4]=6，i=3；继续往后遍历。

i=3，j=4,移动j，直到sum=[2+4+3]=9时，result=j-i+1=3；sum=[4+3]=7，i=4；继续往后遍历。

此时sum=7，result=j-i+1=2；j无法再往后循环，最后最小值为result=2

int minSubArrayLen(int target, int* nums, int numsSize) {if (numsSize == 0) {return 0;}int result = INT_MAX;int i=0,j=0,sum=0;while(j<numsSize){sum += nums[j];while(sum >= target){result=fmin(result,j-i+1);sum -=nums[i];i++;}j++;}return result==INT_MAX ? 0:result;
}

时间复杂度O（n）;空间复杂度O（1）

这篇关于力扣209：长度最小的数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---