数组连续和 - 华为OD统一考试(C卷)

题目描述

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

输入描述

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

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

输出描述

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

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

示例1

输入：
3 7
3 4 7

输出：
4

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

示例2

输入：
10 10000
1 2 3 4 5 6 7 8 9 10

输出：
0

说明：
所有元素的和小于 10000 ，所以返回 0。

 Java代码

第一种暴力法，时间复杂度O(n^2)

package odTest;

import java.util.Arrays;
import java.util.Scanner;

public class continueArraySum {
	static int count = 0;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] condtions = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int[] numArrays = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int count = 0;
		
		for(int i=0;i<condtions[0];i++) {
			int sum = 0;
			for(int j=i;j<condtions[0];j++) {
				sum = sum +numArrays[j];
				if(sum>=condtions[1]) {
					count++;
				}
			}
		}
		System.out.println(count);
	}
}

 第二种双指针法

将下标为1到最后下标之间所有和的情况都保存起来（n[0],n[0]+n[1],n[0]+n[1]+n[2]....），r然后通过r=1下标值减l=0下标值，当结果大于题目所给的限制值的时候，说明r=1下标后的所有都符合条件，然后 count += n-r+1，n为所给的数组长度。然后，r和l依次加1判断下一个连续区间符合条件的个数。

package odTest;

import java.util.Scanner;

public class continueArraySum1 {

	public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 输入数组大小
        int x = scanner.nextInt(); // 输入目标值
        int[] arr = new int[n]; // 定义数组
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt(); // 输入数组元素
        }

        System.out.println(getResult(n, x, arr)); // 调用函数并打印结果

    }

    // 获取结果的方法
    public static int getResult(int n, int x, int[] arr) {
        int[] preSum = new int[n + 1];
        
        //这一步保证从下表为0开始计算
        preSum[0] = 0;
        //将下标从 0-1，0-2，0-3，0-4....0-n的值保存到数组中
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + arr[i - 1]; // 求前缀和
        }
      
        int l = 0;
        int r = 1;
        int ans = 0;

        while (r <= n) {
        	//preSum[r] - preSum[l] 的值代表数组区间的和大小，大于给定的值时，
        	//说明r后面的值累计都会大于给定的值,直接累计到ans就行了，否则r就往后移
            if (preSum[r] - preSum[l] >= x) {
                ans += n - r + 1; // 更新结果
                l++;
                r = l + 1;
            } else {
                r++;
            }
        }

        return ans; // 返回结果
    }
}