连续子区间和

[编程题]连续子区间和

热度指数：3979 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。

输入描述:

第一行两个整数c x（0 < c <= 1000000, 0 <= x <= 100000000)

第二行有c个正整数（每个正整数小于等于100)。

输出描述:

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

示例1

输入

3 6
2 4 7

输出

说明

对于有3个整数构成的数组而言，总共有6个下标连续的区间，他们的和分别为：

2 = 2

4 = 4

7 = 7

2 + 4 = 6

4 + 7 = 11

2 + 4 + 7 = 13

其中有4个和大于等于6，所以答案等于4。

算法知识视频讲解

Java

scutlwy

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();
        int x = sc.nextInt();
        int[] arr = new int[c];
        for(int i = 0; i < c; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(intervalNums(arr, x));
    }
    
    private static long intervalNums(int[] arr, int x){
        // 这里要用long记录，否则只能a45%
        long res = 0;
        int left = 0,  right = 0;
        long sum = arr[left];
        while(left < arr.length){
            // 符合条件则左指针移动，同时sum减去窗口左端值
            if(sum >= x){
                res += arr.length - right;
                sum -= arr[left];
                left++;
            }else{
                // 不符合则右指针向右移动扩大窗口，同时sum加上当前窗口右端值
                // 当窗口右端到达数组末尾则不能扩大。因为窗口都开到最大还不符合，所以可以直接退出
                right++;
                if(right == arr.length){
                    break;    
                }
                sum += arr[right];
            }
        }
        return res;
    }
}

发表于 2020-08-19 17:04:09 回复(0)