网站发展趋势和前景,网站程序模块,wordpress进入后台,ipad可以做网站吗文章目录 【前缀和】美团20230826秋招T5-平均数为k的最长连续子数组题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 【前缀和】美团20230826秋招T5-平均数为k的最长连续子数组
题目描… 文章目录 【前缀和】美团20230826秋招T5-平均数为k的最长连续子数组题目描述与示例题目描述输入描述输出描述示例输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 【前缀和】美团20230826秋招T5-平均数为k的最长连续子数组
题目描述与示例
题目描述
给定n个正整数组成的数组求平均数正好等于k的最长连续子数组的长度。
输入描述
第一行输入两个正整数n和k用空格隔开。
第二行输入n个正整数ai用来表示数组。
1 n 200000
1 k, ai 10^9输出描述
如果不存在任何一个连续子数组的平均数等于k则输出-1。
否则输出平均数正好等于k的最长连续子数组的长度。
示例
输入
5 2
1 3 2 4 1输出
3说明
取前三个数即可平均数为2。
解题思路
求连续子数组的平均数是一个比较难处理的过程可以先做一步转换把原数组nums中每一个元素都减去k得到一个新数组nums_new那么题目就变成了求和为0的最长连续子数组的长度了。
由于nums_new中的元素有负数也有正数该解题过程不能够用滑动窗口来解决而应该使用前缀和结合哈希表来解决问题。
对数组nums_new构建前缀和数组pre_sum_lst由于要求计算和为0的连续子数组故我们仅需要找到pre_sum_lst中两个距离最远的相等元素。该过程可以通过一边遍历pre_sum_lst中的元素pre_sum一边构建哈希表dic来进行若
pre_sum不位于哈希表中说明它是首次出现将其下标i记录在哈希表中pre_sum已位于哈希表中说明它之前已经出现过了第一次出现的下标为dic[pre_sum]那么当前和为0的连续子数组的长度为i-dic[pre_sum]将其与ans比较并更新。
上述过程的核心代码如下
for i, pre_sum in enumerate(pre_sum_lst):if pre_sum not in dic:dic[pre_sum] ielse:ans max(ans, i-dic[pre_sum])代码
Python
# 题目【前缀和】美团2023秋招-平均数为k的最长连续子数组
# 作者闭着眼睛学数理化
# 算法前缀和/哈希表
# 代码有看不懂的地方请直接在群上提问from itertools import accumulate# 输入数组长度n平均值k
n, k map(int, input().split())
# 对输入的数组nums中的每一个元素进行-k的预处理得到nums_new数组
nums_new list(map(lambda x: int(x)-k, input().split()))
# 构建前缀和数组注意首位需要填充一个0表示不选取任何数字的前缀和
pre_sum_lst [0] list(accumulate(nums_new))# 构建哈希表储存每个前缀和首次出现的下标
dic dict()
# 初始化答案为-1
ans -1
# 遍历前缀和数组中的所有下标和元素
for i, pre_sum in enumerate(pre_sum_lst):# 若pre_sum没有在哈希表中出现过# 则记录其第一次出现的下标if pre_sum not in dic:dic[pre_sum] i# 若pre_sum在哈希表中出现过# 则计算当前下标i和其第一次出现下标dic[pre_sum]之差# 用于更新答案anselse:ans max(ans, i-dic[pre_sum])print(ans)Java
import java.util.HashMap;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int k scanner.nextInt();int[] nums new int[n];for (int i 0; i n; i) {nums[i] scanner.nextInt() - k; // 预处理将每个元素减去 k}HashMapInteger, Integer prefixSumIndices new HashMap();prefixSumIndices.put(0, -1); // 初始化前缀和为0的下标为-1int prefixSum 0;int maxLength -1;for (int i 0; i n; i) {prefixSum nums[i];if (prefixSumIndices.containsKey(prefixSum)) {int startIndex prefixSumIndices.get(prefixSum) 1; // 子数组的起始下标int currentLength i - startIndex 1; // 当前子数组长度maxLength Math.max(maxLength, currentLength);} else {prefixSumIndices.put(prefixSum, i);}}System.out.println(maxLength);}
}C
#include iostream
#include vector
#include unordered_mapusing namespace std;int main() {int n, k;cin n k;vectorint nums(n);for (int i 0; i n; i) {cin nums[i];nums[i] - k; // 预处理将每个元素减去 k}unordered_mapint, int prefixSumIndices;prefixSumIndices[0] -1; // 初始化前缀和为0的下标为-1int prefixSum 0;int maxLength -1;for (int i 0; i n; i) {prefixSum nums[i];if (prefixSumIndices.find(prefixSum) ! prefixSumIndices.end()) {int startIndex prefixSumIndices[prefixSum] 1; // 子数组的起始下标int currentLength i - startIndex 1; // 当前子数组长度maxLength max(maxLength, currentLength);} else {prefixSumIndices[prefixSum] i;}}cout maxLength endl;return 0;
}时空复杂度
时间复杂度O(N)。构建nums_new前缀和数组pre_sum_lst遍历前缀和数组pre_sum_lst均只需一次遍历。
空间复杂度O(N)。主要为前缀和数组pre_sum_lst和哈希表dic所占空间。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
