这道题要求我们计算在给定的排列 p
中有多少个 (i, j)
对满足条件:
受到哈希3的启发,我们自然想到从左往右枚举每一个数j , 维护一个前缀哈希表H,那么也就是在i∈[1,j−1] 里寻找有多少个i 满足:
pi+pj=i+j本题为2024年9月1日字节跳动-秋招机考原题
字节跳动机考的介绍点击这里
小红有一个长度为n的排列p,他想知道p中有多少个i,j对满足:i<j且pi+pj=i+j。
请你帮他算算吧。
输入包含两行。
第一行一个正整数n(1≤n≤200000),表示排列的长度。
第二行n个正整数pi(1≤pi≤n),表示排列p。(保证输入是一个排列。)
输出一行一个整数表示好对的个数。
输入
5
2 1 3 5 4
输出
4
说明
p1+p2=2+1,
p1+p5=2+4,
p2+p4=1+5,
p4+p5=4+5。
共这四对。