华为OD机试 - 数组连续和 - 滑动窗口（Java 2024 C卷 100分）

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

二、输入描述

第一行为两个整数 N,x。(0<N≤100000, 0≤x≤10000000)

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

三、输出描述

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

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

1、输入

3 7
3 4 7

2、输出

4

3、说明

第一行的 3表示第二行数组输入3个数，第一行的7是比较数，用于判断连续数组是否大于该数；
组合为 3+4,3+4+7,4+7,7；都大于等于指定的7；所以共四组。

四、解题思路

通过滑动窗口的方式解题。

核心思路：

1. 遍历数组，向右扩展窗口
2. left右移，缩小窗口
   • left右移后，减去left处的值，就是left到right的区间和
   • 再通过区间和去和x比较，如果还是大于x，则left继续右移
   • 满足条件的连续区间个数+1

五、Java算法源码

public class Test05 {public static void main(String[] args) {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 left = 0; // 左指针int right = 0; // 右指针int sum = 0; // 当前窗口内元素的和int count = 0; // 满足条件的连续区间个数// 遍历数组while (right < N) {// 向右扩展窗口sum += nums[right];int tempSum = sum;// left右移，缩小窗口while (tempSum >= x && left <= right) {// left右移后，减去left处的值，就是left到right的区间和// 再通过区间和去和x比较，如果还是大于x，则left继续右移tempSum -= nums[left];left++;// 满足条件的连续区间个数+1count++;}left = 0;right++;}// 输出结果System.out.println(count);}
}

六、效果展示

1、输入

4 7
2 3 4 7

2、输出

6

3、说明

符合要求的连续区间：

234、2347、34、347、47、7

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷+C卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。