思路：双指针

可以参考LeetCode原题： LeetCode 209. 长度最小的子数组

这道题求得不是最小长度，而是方案数，那么每当我们找到一个满足条件的区间$[l,r]$时，$[l,r+1],[l,r+2],...,[l,n-1]$也一定是满足条件的，因此对应的方案数就是$n-r$，其中$n$为数组长度，使用双指针一边移动一边计数即可。

JavaScript代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n, x;
let w = [];

rl.on('line', (line) => {
    const inputs = line.split(' ').map(Number);

    if (n === undefined) {
        [n, x] = inputs;
    } else {
        w = inputs;
        processInput(n, x, w);
        rl.close();
    }
});

function processInput(n, x, w) {
    let ans = 0;
    let l = 0,
        r = 0;
    let sum = 0;

    while (r < n&&l<=r) {
        sum += w[r];
        while (sum >= x) {
            ans += n - r;
            sum -= w[l];
            l += 1;
        }
        r += 1;
    }

    console.log(ans);
}

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取n的值
        int x = scanner.nextInt();  // 读取x的值
        int[] w = new int[n];  // 创建数组w
        long ans = 0;  // 用于统计答案个数
        int l = 0, r = 0;  // 初始化双指针
        int sum = 0;

        // 读取数组w的值
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }

        // 双指针算法
        while (r < n) {
            sum += w[r];
            while (sum >= x&&l<=r) {
                ans += n - r;
                sum -= w[l];
                l++;
            }
            r++;
        }

        // 输出结果
        System.out.println(ans);
    }
}

C++代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;  // 读取n和x的值
    vector<int> w(n);  // 创建数组w
    long long ans = 0;  // 用于统计答案个数
    int l = 0, r = 0;  // 初始化双指针
    int sum = 0;

    // 读取数组w的值
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    // 双指针算法
    while (r < n) {
        sum += w[r];
        while (sum >= x&&l<=r) {
            ans += n - r;
            sum -= w[l];
            l++;
        }
        r++;
    }

    // 输出结果
    cout << ans << endl;

    return 0;
}

Python代码

n,x=map(int,input().split())
w=list(map(int,input().split()))
ans=0  #统计答案个数
l,r=0,0 #双指针
sum=0
while r<n:
    sum+=w[r]
    while sum>=x and l<=r:
        ans+=n-r
        sum-=w[l]
        l+=1
    r+=1
print(ans)

题目描述

给定一个含有N个正整数的数组，求出有多少连续区间（包括单个正整数），它们的和大于等于 $x$。

输入描述

第一行为两个整数 $N$,$x$。($0 < N \le 100000, 0 \le x \le 10000000$)

第二行有 $N$ 个正整数 （每个正整数小于等于 $100$）。

输出描述

输出一个整数，表示所求的个数

注意：此题对效率有要求，暴力解法通过率不高，请考虑高效的实现方式。

样例1

输入

3 7
3 4 7

输出

4

说明：第一行的 $3$表示第二行数组输入 $3$个数，第一行的 $7$是比较数，用于判断连续数组是否大于该数；组合为 $3+4$; $3+4+7$,$4+7$,$7$；都大于等于指定的 $7$；所以共四组。

样例2

输入

10 10000
1 2 3 4 5 6 7 8 9 10

输出

0

说明：所有元素的和小于 $10000$ ，所以返回 $0$。