长度最小的子数组

题目描述

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

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]]，并返回其长度。如果不存在符合条件的子数组，返回 0。

输入格式

第一行包含两个整数 n 和 target，分别表示数组长度和目标和。

第二行包含 n 个正整数 nums[1], nums[2], ..., nums[n]。

输出格式

输出一行一个整数，表示满足条件的最短子数组长度；若不存在则输出 0。

样例输入 #1

6 7
2 3 1 2 4 3

样例输出 #1

2

样例输入 #2

3 4
1 4 4

样例输出 #2

1

样例输入 #3

8 11
1 1 1 1 1 1 1 1

样例输出 #3

0

说明

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

数据范围：

• 1 <= target <= 10^9
• 1 <= n <= 10^5
• 1 <= nums[i] <= 10^4

进阶

如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n log n) 时间复杂度的解法。