8_26 美团笔试t5

平均值等于k的最长连续子数组的长度

给定一个数组arr[]， 长度 为 n， 输入一个值 k，

求该数组 最长的一个连续子数组，其中该子数组 平均值等于k。

例如： n = 5， k = 3， arr[] = [1，3，2，4，3]

那么最终输出 4， 因为[3, 2, 4, 3]的平均值为 3，并且长度最长

思路：采用前缀和 保存当前元素i 和之前的元素之和arr[0] + arr[1] + ... arr[i]。有了这个前缀和以后，可以算出0 ~ i 的平均值情况，但是假如要求的结果不是从0开始，而是从 j开始，也就是j ~ i ，那么这种情况就被忽略，所以还需要加入一个hashmap，用来保存从 0 ~ j的情况。那么hashmap保存的具体值是什么？保存的其实是一个差值： 从 0 ~ j 的元素和 与 j + 1个平均值为k的数之和的差值。具体来说就是 arr[0] + arr[1] + ... + arr[j] - k * (j + 1)，然后保存 差值 --> j。这样的话，在后面假如哪一个前缀和与满足平均值为k的和 差值为 map中的差值，就可以直接拿到该索引，并把索引之前的那一部分给去除掉，那么剩下的部分就是满足均值为k的部分了。

以上面的例子举例

i 0 1 2 3 4

arr[i] 1 3 2 4 3

preSum[i] 1 4 6 10 13

当i = 0时，应该满足1* 3 = 3，但是前缀和只有1，所以差值为2，因此保存map： -2 --> 0

当i = 1时，应该满足2 * 3 = 6，但是前缀和只有4，所以差值为2，但是这时候查map有 -2，所以直接取出来map -2 对应的index = 0，这时候就知道，把0 ~ index（也就是把0这个元素）这一部分去除掉就可以满足均值为3了，但是长度也会相应减去这个index，因此就有result = i - index = 1 - 0 = 1；这时候不用更新map，因为我们需要的是最长子数组

当i = 2时，应该满足 3 * 3 = 9， 但是前缀和只有6,所以差值为3,这时候查map没有-3所以保存map：-3 --> 2

当i = 3时，应该满足 4 * 3 = 12， 但是前缀和只有10,所以差值为2,这时候查map有-2，所以取出来对应的index = 0，然后去除掉它和它之前部分，就满足均值为3，result = 3 - 0 = 3

当i = 4时，应该满足 5 * 3 = 15， 但是前缀和只有13,所以差值为2,这时候查map有-2，所以取出来对应的index = 0，然后去除掉它和它之前部分，就满足均值为3，result = 4 - 0 = 4