美团笔试最后一题题解

本轮笔试除了最后一题略微需要一点思维，其余都很容易。
友情提示：碰到涉及连续数组平均值、和的题，八九不离十要用前缀和。
1. 第一遍遍历数组，得到前缀和数组，假定为pre，数组长度为m+1
2. 题目等价于找出满足(pre[j]-pre[i])/(j-i) ＝ k的最长abs(j-i)。
整理得pre[j] - j*k＝pre[i] - i*k
所以创建一个新的数组dp ＝ [pre[i] - i*k for i in range(m+1)]
3. 题目问题转换到找出数组dp中值相等的最大索引距离，哈希表做即可
总时间复杂度为O(n)