最新华为OD机试真题-连续区间和(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 连续区间和(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎧 连续区间和

问题描述

LYA 在分析一组数据时，需要统计出有多少个连续区间（包括单个元素）的和大于等于给定的阈值 。现在他将这个任务交给你，请你帮忙计算出满足条件的连续区间的数量。

输入格式

第一行包含两个整数 和 ，分别表示数组的长度和阈值。

第二行包含 个正整数，表示给定的数组。

输出格式

输出一个整数，表示满足条件的连续区间的数量。

样例输入1

3 7
3 4 7

样例输出1

4

样例输入2

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

样例输出2

0

数据范围

数组中的每个元素均小于等于 。

题解

本题可以使用双指针的思路来解决，通过维护一个滑动窗口，记录当前窗口内元素的和，并统计满足条件的区间数量。

具体步骤如下：

1. 初始化左右指针 和 ，分别指向数组的起始位置。

2. 将右指针 向右移动，将对应元素加入窗口，并更新窗口内元素的和 。

3. 当 时，说明当前窗口内的元素满足条件，将满足条件的区间数量加上 （因为从当前位置到数组末尾的所有区间都满足条件）。

4. 同时，将左指针 向右移动，缩小窗口，直到 。每次移动左指针时，将对应元素从窗口中移除，并更新 。

5. 重复步骤 2-4，直到右指针 到达数组末尾。

6. 输出满足条件的区间数量。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

n, x = map(int, input().split())
arr = list(map(int, input().split()))

l = r = ans = sum = 0
while r < n:
    sum += arr[r]
    while sum >= x and l <= r:
        ans += n - r