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

全部评论
直接从题意出发,假设某个子数组和为 sum,那么 sum / len = k,sum 利用前缀和计算,len 同理,直接换算为 (sum[j] - sum[i]) / (j - i) = k,再移项 sum[j] - j*k = sum[i] -i *k,问题就转化为遍历到某个 j 时,找到有没有 i 使得上述结果成立,因此需要 map 去存储上述结果,整个思路就是这样。
1 回复 分享
发布于 2023-08-26 21:19 江西

相关推荐

想润的芹菜人狠话不多:把其中一个老总放中间都会得罪另一个
点赞 评论 收藏
分享
8 11 评论
分享
牛客网
牛客企业服务