题面分析

这道题要求我们计算在给定的排列 p 中有多少个 (i, j) 对满足条件：

• $i < j$
• $p_i + p_j = i + j$

受到哈希3的启发，我们自然想到从左往右枚举每一个数$j$ , 维护一个前缀哈希表$H$，那么也就是在$i \in [1 , j - 1]$ 里寻找有多少个$i$ 满足:

而由于在枚举的过程中，我们就已经知道了$j$ , 未知的是$i$ 。那么等式可以转化为:

所以我们

1.在$H$ 里 查询$j - p_j$ 的个数 $H[j-p_j]$

2.往$H$里插入$p_j - j$ 。

3.遍历下一个元素

举例说明

初始情况

arr = [1, 3, 2, 5]
H = {}

1. 当 j = 1 时
   • p_1 = 1, i = 1
   • 我们先查询 H[j - p_j]，即 H[1 - 1] = H[0]。
   • H[0] 还没有出现过，所以结果为 0。
   • 更新哈希表：H 中增加 p_1 - 1 = 1 - 1 = 0，所以 H = {0: 1}。
2. 当 j = 2 时
   • p_2 = 3, i = 2
   • 查询 H[j - p_j] = H[2 - 3] = H[-1]。
   • H[-1] 还没有出现过，所以结果为 0。
   • 更新哈希表：H 中增加 p_2 - 2 = 3 - 2 = 1，所以 H = {0: 1, 1: 1}。
3. 当 j = 3 时
   • p_3 = 2, i = 3
   • 查询 H[j - p_j] = H[3 - 2] = H[1]。
   • H[1] 出现过 1 次，所以结果为 1。
   • 更新哈希表：H 中增加 p_3 - 3 = 2 - 3 = -1，所以 H = {0: 1, 1: 1, -1: 1}。
4. 当 j = 4 时
   • p_4 = 5, i = 4
   • 查询 H[j - p_j] = H[4 - 5] = H[-1]。
   • H[-1] 出现过 1 次，所以结果为 1。
   • 更新哈希表：H 中增加 p_4 - 4 = 5 - 4 = 1，所以 H = {0: 1, 1: 2, -1: 1}。

总结结果

最终，我们得到了满足条件的 (i, j) 对的数量为：

• 对于 j = 2，没有符合条件的对，结果为 0。
• 对于 j = 3，找到了 1 个符合条件的对，结果为 1。
• 对于 j = 4，找到了 1 个符合条件的对，结果为 1。

所以，总共有 2 个符合条件的 (i, j) 对。

时间复杂度分析：

• 我们遍历一次数组，并使用哈希表进行快速查找和更新。哈希表的插入和查询操作的平均时间复杂度为 O(1)
• 因此，整个算法的时间复杂度为 O(n)。

代码实现

def count_pairs(n, p):
    # 创建一个哈希表，用于记录 p_i - i 出现的次数
    diff_count = {}
    # 结果变量，记录符合条件的(i, j)对数
    result = 0
    
    for j in range(n):
        # 计算 j - p_j
        diff = (j + 1) - p[j]
        # 如果 -diff 已经出现过，那么就说明存在符合条件的 i
        if -diff in diff_count:
            result += diff_count[-diff]
        
        # 更新 diff_count
        if diff in diff_count:
            diff_count[diff] += 1
        else:
            diff_count[diff] = 1
    
    return result

# 输入读取
n = int(input())
p = list(map(int, input().split()))

# 调用函数并输出结果
print(count_pairs(n, p))

本题为2024年9月1日字节跳动-秋招机考原题

字节跳动机考的介绍点击这里

题目内容

小红有一个长度为$n$的排列$p$，他想知道$p$中有多少个$i,j$对满足:$i< j$且$p_i+p_j=i+j$。

请你帮他算算吧。

输入描述

输入包含两行。

第一行一个正整数$n(1≤n≤200000)$，表示排列的长度。

第二行$n$个正整数$p_i(1≤p_i≤n)$，表示排列$p$。(保证输入是一个排列。)

输出描述

输出一行一个整数表示好对的个数。

样例1

输入

5
2 1 3 5 4

输出

4

说明

$p_1+p_2=2+1$，

$p_1+p_5=2+4$，

$p_2+p_4=1+5$，

$p_4+p_5=4+5$。

共这四对。