返回目录

题目描述

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

输入描述

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

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

输出描述

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

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

示例：

题目解析

区间和，最快的计算方式就是利用：一维前缀和。

Python算法源码

def main():
    # 读取输入的 n 和 x
    n, x = map(int, input().split())

    # 读取输入的数组
    nums = list(map(int, input().split()))

    # 计算前缀和
    pre_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + nums[i - 1]

    # 初始化左右指针和结果变量
    l = 0
    r = 1
    ans = 0

    # 双指针算法
    while r <= n:
        if pre_sum[r] - pre_sum[l] >= x:
            # 如果当前区间和大于等于 x，则更新结果并移动左指针
            ans += n - r + 1
            l += 1
            r = l + 1
        else:
            # 否则移动右指针
            r += 1

    # 打印结果
    print(ans)

if __name__ == "__main__":
    main()

C语言算法源码

#include <stdio.h>

void main() {
    // 读取输入的 n 和 x
    int n, x;
    scanf("%d %d", &n, &x);

    // 读取输入的数组
    int nums[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 计算前缀和
    int pre_sum[n + 1];
    pre_sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        pre_sum[i] = pre_sum[i - 1] + nums[i - 1];
    }

    // 初始化左右指针和结果变量
    int l = 0;
    int r = 1;
    long ans = 0;

    // 双指针算法
    while (r <= n) {
        if (pre_sum[r] - pre_sum[l] >= x) {
            // 如果当前区间和大于等于 x，则更新结果并移动左指针
            ans += n - r + 1;
            l++;
            r = l + 1;
        } else {
            // 否则移动右指针
            r++;
        }
    }

    // 打印结果
    printf("%ld\n", ans);
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 读取输入的 n 和 x
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();

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

        // 计算前缀和
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        // 初始化左右指针和结果变量
        int l = 0;
        int r = 1;
        long ans = 0;

        // 双指针算法
        while (r <= n) {
            if (preSum[r] - preSum[l] >= x) {
                // 如果当前区间和大于等于 x，则更新结果并移动左指针
                ans += n - r + 1;
                l++;
                r = l + 1;
            } else {
                // 否则移动右指针
                r++;
            }
        }

        // 打印结果
        System.out.println(ans);
    }
}