【微众银行秋招】230903三、平均值 ＜前缀和＞

平均值

小明有一个数组。他挑选了一个有理数u/v，现在他想知道这个数组有多少个子区间的平均值恰好等于u/v。数组的子区间即是数组中连续的一段区间，如数组[4,2,6]有6个子区间[4],[2],[6],[4,2],[2,6],[4,2,6]。

输入描述
第一行有三个整数 n,u,v(1<=n,v<=100000,1<=u<=n*v)，代表数组的长度，小明选择的有理数的分子和分母。输入保证 u 和 v 的最大公因数是1，即u/v是最简分数。
第二行有n个绝对值不超过1000000的整数，代表数组中的元素。
数字间两两有空格隔开。

输出描述
输出一个非负整数，代表所求的答案

样例输入

6 5 2
2 4 1 3 2 3
1
2

样例输出

6
1

题解

暴力（82%）

import java.util.*;

public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int u = in.nextInt();
        int v = in.nextInt();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int result = countSubarrays(arr,u,v);
        System.out.println(result);

    }

    static int countSubarrays(long[] arr,int u,int v){
        int n = arr.length;
        int count = 0;

        for (int i = 0; i < arr.length; i++) {
            long curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += arr[j];
                if(u*(j-i+1) == v*curSum){
                    count++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

前缀和（一维）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double u = in.nextDouble();
        double v = in.nextDouble();
        double[] nums = new double[n];

        for (int i = 0; i < n; i++) {
            nums[i] = in.nextDouble();
        }

        int res = 0;
        double[] pre = new double[n + 1];
        //前几项的和为多少
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }

        /*for (double i:pre) {
            System.out.print(i+" ");
        }
        System.out.println();*/

        for (int left = 0; left < n; left++) {
            for (int right = (int) (left + v - 1); right < n; right += v) {
                if (v * (pre[right + 1] - pre[left]) == (right - left + 1) * u) {
                    res++;
                }
            }
        }
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36