[编程题]平均数为k的最长连续子数组
前缀和+哈希表思路：将输入数组中的元素减去k可将题目转化为“和为0的最长连续子数组”。进一步，为省去重复计算，使用前缀和处理数组。使用哈希表记录前缀和数组中每个值第一次出现的位置，遍历数组找到相同的值便计算距离并更新最大值即可。上述前缀和数组可优化为一个变量。python参考代码：
import s
展开全文
先将数组里面的每个数都减 ，然后找最长的和为 的连续段，我们用前缀和加速，设数组 为前缀和数组，对于每个 我们只需要找到 数组最靠前的值为 的位置即可，这个用 存一下即可。
#include<bits/stdc++.h>
#define int long long
#def
展开全文
题意给定n个正整数组成的数组，求平均数正好等于 k 的最长连续子数组的长度。思路某个连续子数组的平均数等于k可以转化为区间和等于k*(j-i+1)如果用前缀和维护的话就是sum[j] - sum[i-1] = k * (j-i+1)这里有个很巧妙的地方就是把每个数都减去k，这样就变成了sum[j]-
展开全文
当长为 len 的平均数等于 k 时，代表区间的和为 len*k ，特别的，当 k 为 0 时，区间的和也为0，代表 sum[r] == sum[l-1] ，所以我们可以先简化题意，将每一项都减去 k ，来求区间平均数为 0 的最长区间，那么对于每个区间前缀和 sum ，一定是和之前值等于 sum
展开全文
from itertools import accumulate
n,k=map(int,input().split())
number=list(map(int,input().split()))
for i in range(n):
number[i]-=k
number1=list(a
展开全文
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef
展开全文
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include &l
展开全文
思路：将输入数组的每个元素减去k，即可将题目转化为求“和为0的最长连续子数组”。使用前缀和的思想，我们维护一个变量sum。并用哈希表记录前缀和为sum的最小位置。假设前i个元素和为sum，前j个元素和也为sum，那么毫无疑问，第i+1个元素开始直到第j个元素之和必然为0。根据这个思路，我们遍历一遍数
展开全文
同时减去k后， 求最长连续子数组和为0的值即可
代码：
using namespace std;
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e5 + 10;
const int MOD = 998244
展开全文
问题信息
相关试题
-
评论(8) 来自2023年美团秋招编程岗...
-
评论(7) 来自2023年美团秋招编程岗...
-
评论(10) 来自2023年美团秋招编程岗...
-
评论(10) 来自2023年美团秋招编程岗...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
