思路：双指针

本题把题目拆解开，就是Leetcode原题：209. 长度最小的子数组 - 力扣（LeetCode）

求$\ge K$的最短子数组

时间复杂度

$O(n)$

c++代码

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int n, target;
    cin >> n >> target;
    vector<int> vt(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> vt[i];
    }
    int ans = INT_MAX, cnt = 0;
    for (int l = 0, r = 0; r < n; cnt -= vt[l], l++)
    {
        while (r < n && cnt < target)
        {
            cnt += vt[r];
            r++;
        }
        if (cnt >= target)
        {
            ans = min(ans, r - l);
        }
    }
    cout << ans;
    return 0;
}

python代码

n = int(input())
k = int(input())
arr =[]
for i in range(n):
    x = int(input())
    arr.append(x)
i = 0
j = 0
s = 0
ans = 10**9
while i < n:
    while j<n and s < k:
        s += arr[j]
        j += 1
    if s >= k :
        ans = min(ans, j-i)
    s -= arr[i]
    i += 1
print(ans)

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int i = 0, j = 0;
        int sum = 0;
        int ans = n;
        while (j<n) {
            sum+=arr[j];

            while(sum>=k){
                ans = Math.min(ans, j - i + 1);
                sum-=arr[i];
                i++;
            }
            j++;
            

        }

        System.out.println(ans);

    }
}

题目描述

小红这天在游戏厅里快乐地玩耍。

他发现一个特别容易获得奖品的游戏，每次会有游戏机会弹出$N$个标靶， 根据标靶的大小从大到小按照1，2，3…$N$顺序编号，每个标靶会有一定的分数（分数均小于等于10）。小红每一轮可以投入游戏币来决定他的射击次数，且每一轮小红只会选择连续的标靶（因为这样更容易射中）进行射击。最终得分之和大于等于 $K$ 即可获得奖品。

由于小红的枪法百发百中，因此他只需要确定自己最少需要多少枚游戏币才能中奖。 另外由于前面的标靶更大更容易打中，因此如果有多种不同的打法，小红会倾向选择前面的标靶进行射击。

请问小红需要花费多少币才可以拿到奖品。

输入描述

输入第一行为标靶总数$N$；

输入为第二行满足获奖的最小得分$K$；

接下来$N$行： $N$个标靶的分数(分数不超过10)

输出描述

样例

样例输入

5
20
5
6
7
8
9

样例输出

3

说明 按照从左往右顺序挑选, 6+7+8>20, 所以2号、3号、4号三名选手获奖。