题目内容

给定一个正整数数组$a_1,a_2,...,a_n$，求平均数正好等于k的最长连续子数组的长度

思路：前缀和

给定一个数组，要求找到一个连续子数组的平均值为$k$，并且其长度是符合条件子数组里最长的，求其长度。

可以考虑前缀和的做法来解此题。要求连续子数组平均值为$k$，让每个数$a_i^{、}=a_i-k$，那么如果一段连续子数组平均值和为$k$，则这一段数组的和为$0$。$\sum{a_i^{、}=\sum{a_i}-k*length}=0$。

扩展开来，如果前缀和中出现某两个位置的值相等，那么根据前缀和的定义，他们间的这一段的和为$0$，那么这一段的长度就是备选答案之一。

所以我们需要使用哈希来存储前缀和中每个数第一次出现的位置，当其又一次出现时，就可以计算长度作为备选答案。