最新华为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
        sum -= arr[l]
        l += 1
    r += 1

print(ans)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        int l = 0, r = 0;
      	long ans = 0, sum = 0;
        while (r < n) {
            sum += arr[r];
            while (sum >= x && l <= r) {
                ans += n - r;
                sum -= arr[l];
                l++;
            }
            r++;
        }
        
        System.out.println(ans);
    }
}

• Cpp

#include <iostream>
using namespace std;

const int N = 1e5 + 5;
int n, x;
int arr[N];


int main() {
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int l = 0, r = 0;
  	long long ans = 0, sum = 0;
    while (r < n) {
        sum += arr[r];
        while (sum >= x && l <= r) {
            ans += n - r;
            sum -= arr[l];
            l++;
        }
        r++;
    }
    
    cout << ans << endl;
    return 0;
}