题解 | 谐距下标对

# n=int(input())
# print(n)
# number_list=[0]
# for i in list(map(int,input().split())):
#     number_list.append(i)
# # print(number_list)
# result=0
# j=0
# while n>0:
#     j=n-1
#     while j>0:
#         if number_list[n] - number_list[j] == n - j:
#             result +=1
#         j-=1
#     n-=1
# print(result)
# 上面的方法由于暴力枚举，算法复杂度为n方，当数据达到100000时，程序无法在1s内运行结束，固需要优化

# number_list[j] -number_list[j] = j-i  等价于 number_list[j] -j = number_list[i] -i
# 故可以换一个思路，标记 number_list[m]-m出现的次数，将 number_list[m]-m 作为键值对写入字典，每次遍历时更新number_list[m]-m对应的值

n = int(input())
number_list = list(map(int, input().split()))
count = {}
result = 0 

for i in range(0,n):
    k = number_list[i] - i              # 计算所有的k=number_list[i]-i,把所有的k出现的次数统计在字典中
    if k in count:						# 如果k不是首次出现，则将k对应的值加1
        count[k] +=1
    else:
        count[k] =0						#如果k是首次出现，则将k添加为键，且设置其对应的值为0
    result += count[k]					#遍历到i=m时，如果此时的k(number_list[m]-m)已经在字典count的键中，则说明此时有count[k] 个 number_list[i]-i 与number_list[m]-m 相等，即有count[k]个谐距下标对，对count[k]进行累加得到result

print(result)