#3811. 练2-最短魔法序列

练2-最短魔法序列

🏫 兔猫信奥学院:最短魔法序列

在兔猫信奥学院的一堂魔法数据课上,加菲老师带来了一项新任务。
他告诉小兔和小猫:“我这里有一串神奇的正整数序列,每个数字代表一种魔法能量。若你们能从中找出一段连续的子数组,使得该子数组内的魔法能量总和至少达到 targettarget,且这段子数组的长度尽可能短,就能获得开启知识宝盒的钥匙!”

小兔和小猫开始了紧张的实验,他们需要找到满足条件的最短魔法序列,并返回该序列的长度。如果没有一段序列能达到targettarget,则任务失败,返回0。


💡【题目描述】

给定一个包含 nn 个正整数的数组和一个正整数 targettarget

找出该数组中满足其累加总和大于等于 targettarget长度最小的子数组 [numsl,numsl+1,,numsr][nums_l, nums_{l+1}, \ldots, nums_r],并返回其长度。如果不存在符合条件的子数组,返回 00


📥【输入格式】

  • 第一行包含两个正整数 nntargettarget,其中
    • nn 表示数组中元素的个数,
    • targettarget 表示目标魔法能量值。
  • 第二行包含 nn 个正整数,数组 numsnums 的各个元素,数字之间以空格分隔。

📤【输出格式】

  • 输出一个整数,表示满足累加和大于等于 targettarget 的最短子数组的长度;若不存在这样的子数组,则输出 00

📌【数据范围】

  • 1target1091 \le target \le 10^9
  • 1n1051 \le n \le 10^5
  • 1nums[i]1041 \le nums[i] \le 10^4

💡【输入输出样例】

样例输入 1

6 7
2 3 1 2 4 3

样例输出 1

2

说明:子数组 [4,3][4,3] 的总和为 77,是满足条件的最短魔法序列。


样例输入 2

3 4
1 4 4

样例输出 2

1

说明:单个数字 44 已满足条件。


样例输入 3

8 11
1 1 1 1 1 1 1 1

样例输出 3

0

说明:不存在满足累加和大于等于 1111的子数组。