写作绅士,读作丧尸 X岛揭示板
顺猴者昌 逆猴者亡 首页版规 |用户系统 |移动客户端下载 | 丧尸路标 | | 常用图串及路标 | 请关注 官方公众号:【X岛揭示板】 官方微博: 【@X岛极速版】| 人,是会思考的芦苇
常用串:·豆知识·跑团板聊天室·公告汇总串·X岛路标

No.58574554 - 无标题 - 技术宅


回应模式
No.58574554
名 称
E-mail
标题
颜文字
正文
附加图片
•程序语言、压制投稿、视频制作以及各计算机领域的技术问题
•我觉得还是CSDN靠谱一点
•本版发文间隔为15秒。

无标题 无名氏 2023-07-12(三)17:45:17 ID:TcPVBay [举报] [订阅] [只看PO] No.58574554 [回应] 管理
求助各位肥哥一个算法问题:
给你一个长度为n的整数序列A,问你在A中有多少个区间中所有数的和等于m
n<2e5,m<1e9
无标题 无名氏 2023-07-12(三)18:08:12 ID:iZ6aYZ6 [举报] No.58574913 管理
记录区间左右端点,内部和小于就往右多扩一位,大于就左边缩一位
无标题 无名氏 2023-07-12(三)18:43:12 ID:qQlsZaQ [举报] No.58575467 管理
>>No.58574913
正确的,o(n)
无标题 无名氏 2023-07-12(三)21:19:22 ID:YloHKCX [举报] No.58577816 管理
>>No.58574913
但这样不是只能找到一个区间吗?所以找到了之后从左边端点+1继续向右找?那可能不止O(n)了吧
无标题 无名氏 2023-07-12(三)21:25:20 ID:PbnZU4X [举报] No.58577910 管理
正整数还是只是整数?
无标题 无名氏 2023-07-12(三)21:52:38 ID:p2upr3H [举报] No.58578394 管理
>>No.58574913
这样?

int f(int n,int* A,int m){
int l = 0;
int r = 0;
int s = 0;
int ans = 0;
while(r<=n){
if (s<m){
s+=A[r];
r++;
}
else if (s>m){
s-=A[l];
l++;
}
else if (s==m){
ans++;
s+=A[r];
r++;
continue;
}
}
return ans;
}
无标题 无名氏 2023-07-12(三)21:53:24 ID:e0JGM8m [举报] No.58578410 管理
```julia
function f58574554(A::AbstractVector{<:Integer}, m::Integer)
  d = Dict(0 => 1)
  c = 0
  for k = cumsum(A)
    c += get(d, k-m, 0)
    d[k] = get(d, k, 0) + 1
  end
  return c
end
f58574554([1,2,3,-2,-1,5], 3) # 4
```
无标题 无名氏 2023-07-12(三)21:57:16 ID:p2upr3H [举报] No.58578480 管理
>>No.58578394
c/c++
但排版...吞空格是吧?
无标题 无名氏 2023-07-12(三)21:59:01 ID:KX7teW0 [举报] No.58578507 管理
>>No.58574913
不是正整数
无标题 无名氏 2023-07-12(三)22:15:24 ID:TcPVBay (PO主) [举报] No.58578774 管理
感谢(〃∀〃)
无标题 无名氏 2023-07-12(三)22:18:14 ID:Xgbo6j9 [举报] No.58578824 管理
>>No.58578507
你要能确定最小值,或者翻转一下确定最大值位置,不是正整数不也能用吗?
收起 查看大图 向左旋转 向右旋转
无标题 无名氏 2023-07-12(三)23:34:02 ID:YgXsGaY [举报] No.58580235 管理
这样怎么样...
无标题 无名氏 2023-07-13(四)14:04:41 ID:YgXsGaY [举报] No.58587808 管理
>>No.58580235
(;´Д`)
无标题 无名氏 2023-07-14(五)23:38:04 ID:noqEbAp [举报] No.58612815 管理
如果都是正整数,那么每个数作为区间左端点最多有一个符合条件的区间,可以从它一直向右找到>=m的位置,然后左端点移动一格右边继续找,整体是线性的;
但是如果有负数,那么符合条件的区间总共可能有平方个!比如1和-1交替出现,那么随便一个长度为奇数的区间,和都是1或-1!
这时候大概只能n logn复杂度了,一种办法是分治,首先把整个数组算前缀和s[i],问题就变成有哪些i<=j满足s[j]-s[i]=m,如果随便选取一个中间点k,那么要找所有跨过了k的符合条件的区间,可以先左右分别排序,然后一遍扫过去,然后递归寻找左右内部的符合条件的区间
无标题 无名氏 2023-10-09(一)13:21:58 ID:TcPVBay (PO主) [举报] No.59792503 管理
1[1,2]
无标题 无名氏 2023-10-09(一)17:44:52 ID:bWO3KdY [举报] No.59794820 管理
>>No.58577816

找完一个接着往后滑嘛

UP主: