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

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

给定一个含有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) {
                    r = m; // 更新右边界
                } else {
                    l = m; // 更新左边界
                }
            }

            // psum[r] - psum[s] == sum(a[s:r])
            // sum(a[s:r]) >= x 则 从s到 [r ~ n]的区间都满足条件
            if (psum[r] - psum[s] >= x) {
                rs += n - r + 1; // 更新结果
            }
        }

        System.out.println(rs);
    }
}

Python

n, x = map(int, input().split())
a = list(map(int, input().split()))
psum = [0] * (n + 1)

for i in range(n):
    psum[i + 1] = psum[i] + a[i]

rs = 0
for s in range(n):
    l, r = s, n
    while l + 1 < r:
        m = (l + r) // 2
        if psum[m] - psum[s] >= x:
            r = m
        else:
            l = m

    # psum[r] - psum[s] == sum(a[s:r])
    # sum(a[s:r]) >= x 则 从s到 [r ~ n]的区间都满足条件
    if psum[r] - psum[s] >= x:
        rs += n - r + 1

print(rs)

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<long long> psum(n + 1, 0LL);

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

    long 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) {
                r = m;   // 更新右边界
            } else {
                l = m;   // 更新左边界
            }
        }

        // psum[r] - psum[s] == sum(a[s:r])
        // sum(a[s:r]) >= x 则 从s到 [r ~ n]的区间都满足条件
        if (psum[r] - psum[s] >= x) {
            rs += n - r + 1;   // 更新结果
        }
    }

    cout << rs << endl;
    return 0;
}