首页 > 试题广场 >

平均数为k的最长连续子数组

[编程题]平均数为k的最长连续子数组
  • 热度指数:3374 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定n正整数组成的数组,求平均数正好等于 k 的最长连续子数组的长度。

输入描述:
第一行输入两个正整数nk,用空格隔开。
第二行输入n个正整数a_i,用来表示数组。




输出描述:
如果不存在任何一个连续子数组的平均数等于k,则输出-1。
否则输出平均数正好等于 k 的最长连续子数组的长度。

示例1

输入

5 2
1 3 2 4 1

输出

3

说明

取前三个数即可,平均数为2。
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt(), ans = -1;
        long res = 0;
        int[] a = new int[n+5];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        Map<Long, Integer> b = new HashMap<>();
        b.put(0L, 0);
        for (int i = 1; i <= n; i++) {
            res += a[i] - k;
            if (b.containsKey(res)) {
                ans = Math.max(ans, i - b.get(res));
            } else {
                b.put(res, i);
            }
        }
        System.out.print(ans);
    }
}

发表于 2024-11-26 21:51:46 回复(0)