题目描述

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

输入描述

第一行两个整数N x（0 < N <= 100000, 0 <= x <= 10000000)

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

输出描述

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

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

示例：

C算法源码

// C语言 控制台输入获取
#include <stdio.h>

// 获取结果的函数
int getResult(int n, int x, int arr[]) {
    int preSum[n+1];

    preSum[0] = 0;
    for (int i = 1; i <= n; i++) {
        preSum[i] = preSum[i - 1] + arr[i - 1];
    }

    int l = 0;
    int r = 1;
    int ans = 0;

    while (r <= n) {
        if (preSum[r] - preSum[l] >= x) {
            ans += n - r + 1;
            l++;
            r = l + 1;
        } else {
            r++;
        }
    }

    return ans;
}

int main() {
    int n, x;
    scanf("%d %d", &n, &x); // 输入数组大小和目标值
    int arr[n]; // 定义数组

    // 输入数组元素
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // 调用函数并打印结果
    printf("%d\n", getResult(n, x, arr));

    return 0;
}

Python算法源码

def get_result(n, x, arr):
    pre_sum = [0] * (n + 1)
  
    pre_sum[0] = 0
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + arr[i - 1]
    
    l = 0
    r = 1
    ans = 0
  
    while r <= n:
        if pre_sum[r] - pre_sum[l] >= x:
            ans += n - r + 1
            l += 1
            r = l + 1
        else:
            r += 1
        
    return ans

# 主函数
if __name__ == "__main__":
    n, x = map(int, input().split()) # 输入数组大小和目标值
    arr = list(map(int, input().split())) # 输入数组元素

    # 调用函数并打印结果
    print(get_result(n, x, arr))

Java算法源码

// Java Scanner 控制台输入获取
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 输入数组大小
        int x = scanner.nextInt(); // 输入目标值
        int[] arr = new int[n]; // 定义数组
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt(); // 输入数组元素
        }

        System.out.println(getResult(n, x, arr)); // 调用函数并打印结果

    }

    // 获取结果的方法
    public static int getResult(int n, int x, int[] arr) {
        int[] preSum = new int[n + 1];

        preSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + arr[i - 1]; // 求前缀和
        }

        int l = 0;
        int r = 1;
        int ans = 0;

        while (r <= n) {
            if (preSum[r] - preSum[l] >= x) {
                ans += n - r + 1; // 更新结果
                l++;
                r = l + 1;
            } else {
                r++;
            }
        }

        return ans; // 返回结果
    }
}