题意

给定n个正整数组成的数组，求平均数正好等于 k 的最长连续子数组的长度。

思路

某个连续子数组的平均数等于k可以转化为区间和等于k*(j-i+1)

如果用前缀和维护的话就是sum[j] - sum[i-1] = k * (j-i+1)

这里有个很巧妙的地方就是把每个数都减去k，这样就变成了sum[j]-sum[i-1] = 0

可以用哈希表维护 mp[x]表示前缀和为x的最早出现的位置

代码

package main

import (
    "fmt"
)

func main() {
    //sum[j] - sum[i-1] = k*(j-i+1)
    var n,k int 
    fmt.Scan(&n,&k)
    a := make([]int,n+1)
    for i := 1; i <= n; i ++ {
        fmt.Scan(&a[i])
    }
    mp := make(map[int]int)
    sum := 0
    ans := 0
    mp[0] = 0
    for i := 1; i <= n; i ++ {
        sum += a[i] - k
        if pos,ok := mp[sum]; ok {
            if ans < i - pos  {
                ans = i - pos 
            }
        }else{
            mp[sum] = i 
        }
    }
    if ans == 0 {
        ans = -1
    }
    fmt.Println(ans)
}