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