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

快来打我* 2024-04-17 10:29 79阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][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、输出 ####

#### 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++;
                    // 满足条件的连续区间个数+1
                    count++;
                }
    
                left = 0;
                right++;
    
            }
    
            // 输出结果
            System.out.println(count);
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

4 7  
2 3 4 7

#### 2、输出 ####

#### 3、说明 ####

符合要求的连续区间：

234、2347、34、347、47、7

![在这里插入图片描述][29cce63b6e60473390d37086d52660fd.bmp_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

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

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

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/24bed13bd8e840cd940db589de4d243a.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[29cce63b6e60473390d37086d52660fd.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/29cce63b6e60473390d37086d52660fd.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/bbe2fccec9624b39b784bbcc7768701f.gif