数组连续和 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

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

输入描述

第一行为两个整数 N,x。(0<N≤100000, 0≤x≤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。

题解

此题可以使用二分查找的方法来解决。

首先计算前缀和数组psum，然后对于每个起始位置s，使用二分查找找到满足条件的第一个右边界r，然后更新结果（累加从s开始连续区间（包括单个正整数）它们的和大于等于x 的个数）。

时间复杂度为O(nlogn)，空间复杂度为O(n)。

Java

import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), x = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        long[] psum = new long[n + 1];

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

        long rs = 0;
        for (int s = 0; s < n; s++) {
            int l = s, r = n;
            while (l + 1 < r) {
                int m = (l + r) / 2;
                if (psum[m] - psum[s] >= x)