首页 > 试题广场 >

谐距下标对

[编程题]谐距下标对

热度指数：7537 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数数组 $\{a_1,a_2,\dots,a_n\}$ 。若下标满足 $i<j$ 且 $a_j-a_i = j-i$ ，则称 $(i,j)$ 为一对谐距下标对。

$\hspace{15pt}$ 请计算数组中的谐距下标对数量。

输入描述:

第一行输入整数 。
第二行输入  个整数 。

输出描述:

输出一个整数，表示谐距下标对数量。

示例1

输入

6
1 2 3 4 5 6

输出

算法知识视频讲解

Java

BraveCoder

import java.util.*;

// 类名必须为 Main，符合题目要求
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取数组长度n，用int即可（题目约束n≤1e5，未超出int范围）
        int n = in.nextInt();

        // 1. Map的键（ai - i）改为Long，值（频次）也改为Long（避免频次累计溢出）
        Map<Long, Long> countMap = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            int ai = in.nextInt(); // ai≤1e5，用int安全，后续转换为Long计算
            // 2. 计算特征值key：强制转换ai为Long，避免ai - i溢出
            Long key = (long) ai - i;
            // 3. 频次累计：用Long存储频次，getOrDefault默认值0L（Long类型）
            countMap.put(key, countMap.getOrDefault(key, 0L) + 1L);
        }

        // 4. 结果变量count改为Long，确保累加过程不溢出
        Long count = 0L;

        // 5. 遍历Map的值（Long类型频次），计算组合数
        for (Long freq : countMap.values()) {
            // 组合数公式：freq*(freq-1)/2，所有操作数均为Long，避免溢出
            count += freq * (freq - 1) / 2;
        }

        // 输出结果（Long类型可直接打印）
        System.out.println(count);
    }
}

发表于 2025-08-31 17:36:27 回复(0)

dhsajds

所以和排序有什么关系呢？？？

发表于 2026-01-22 14:01:00 回复(0)

C++

呆瓜不呆

第一次没通过的原因是计数变量c没有改成long long ，使用int造成了数据溢出。

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin>>n;
    long long c=0;
    unordered_map<int , int> mp;
    for (int i=1; i<=n; i++) {
        int a;
        cin>>a;
        mp[a-i]++;
    }

    for(auto a:mp){
        int n=a.second;
        if(n>=2){
          c+=n*(n-1)/2;
        }

    }

    cout<<c;

}
// 64 位输出请用 printf("%lld")

发表于 2025-08-06 15:36:15 回复(1)

水力发电

暴力超时也能算入门难度？

发表于 2026-02-03 17:17:30 回复(0)

甲醇苯酚钠

#include <iostream>
using namespace std;
#include<vector>
#include<map>
#define ll long long
int main(){
    vector<ll>v;
    map<ll,ll>m;
   ll n;
   ll sumpair=0;
   cin>>n;
   for(int i=0;i<n;i++){//Aj-Ai=j-i 变形为 Aj-j=Ai-i 
    int a;              // 当（i,j）为谐距下标对 An-n一定相等
     cin>>a;            //  统计 An-n次数count   根据组合C 可组合出count!/2*1    
    v.push_back(a);
   }
   for(int i=0;i<n;i++){
      m[v[i]-i]++; 
   }
   for(auto [val,count]:m){
       if(count>1){
          sumpair+=(count*(count-1))/2;
       }
   }
   cout<<sumpair;

}
///////暴力算法超时
// #include <iostream>
// using namespace std;
// #include<vector>

// int main() {
//    vector<int>v;
//    int n;
//    long long sum=0;
//    cin>>n;
//    for(int i=0;i<n;i++){
//     int a;
//     cin>>a;
//     v.push_back(a);
//    }
//    for(int i=0;i<n;i++){
//     for(int j=i+1;j<n;j++){
//         if(v[j]-v[i]==j-i){
//              sum++;
//         }
//     }
//    }
//    cout<<sum;
// }
// // 64 位输出请用 printf("%lld")

发表于 2026-01-20 22:40:44 回复(0)

牛客750916662号

n = int(input())

a = list(map(int,input().split()))

count_dict = {}

for i in range(n):

diff = a[i]-(i+1)

if diff in count_dict:

count_dict[diff] += 1

else:

count_dict[diff] = 1

result = 0

for count in count_dict.values():

if count >1:

result += count*(count-1)//2

print(result)

发表于 2026-01-13 14:55:38 回复(0)

Sinking_sub

n=int(input());aa=[int(x) for x in input().split()]
from collections import Counter
mm=[aa[i]-i for i in range(n)]
print(sum(cnt*(cnt-1)//2 for cnt in Counter(mm).values()))

发表于 2026-01-13 11:31:17 回复(0)

C++

天才hantai少女

数学变形简化条件为aj−j=ai−i，把an-n看成一个整体key，用哈希表计算不同的key分别出现几次，再对每个key的出现次数进行组合数就和

//注意要把int 改为ll

#include<iostream>

#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin>>n;
unordered_map<int,int>cnt;
vector<int>nums(n);
vector<int>processed;
for(int i = 0; i < n;i++){
cin>>nums[i];
ll key = nums[i] - i;
processed.push_back(key);
}
for(int num : processed){
cnt[num]++;
}
ll count = 0;
for(auto pair : cnt){
ll cur = pair.second;
count += cur * (cur - 1) / 2;
}
cout<<count<<'\n';
}

发表于 2025-12-25 22:42:05 回复(0)

阿福的牛客

#include <stdio.h>

#include<limits.h>

#include <stdlib.h>

int main() {

int n;

scanf("%d",&n);

int arr[n];

long count=0;

int max=INT_MIN,min=INT_MAX;

for(int i=0;i<n;i++){

scanf("%d",&arr[i]);

if(arr[i]-i>max){

max=arr[i]-i;

}

if(arr[i]-i<min){

min=arr[i]-i;

}

int range=max-min+1;

int*han=calloc(range,sizeof(int));

for(int i=0;i<n;i++){

han[arr[i]-i-min]++;

}

for(int i=0;i<range;i++){

if(han[i]>=2){

count+=(long)han[i] * (han[i] - 1) / 2;

}

printf("%ld",count);

return 0;

}

发表于 2025-12-05 11:18:36 回复(0)

Python3

三文鱼在发呆

from collections import Counter

n = int(input())
numbers = list(map(int, input().split()))

b = [numbers[i] - (i+1) for i in range(n)]
counter = Counter(b)
count = 0
for freq in counter.values():
    if freq >1:
        count += freq*(freq - 1) //2
print(count)

发表于 2025-10-25 23:44:22 回复(0)

牛客310012745号

from collections import Counter

n = int(input())

# n = 6

input_str = input()

a = [int(x) for x in input_str.split()]

# a = [1 ,2 ,3,4,5 ,6]

match_cnt = 0

for i in range(n):

a[i] = a[i] - i

# 统计每个元素的个数

counter = Counter(a)

#print(counter)

# 输出: Counter({2: 4, 1: 3, 3: 2, 4: 1, 5: 1})

# 获取特定元素的个数

# print(f"元素1的个数: {counter[1]}")

# print(f"元素2的个数: {counter[2]}")

# print(match_cnt)

for element in counter:

if counter[element] > 1:

match_cnt += counter[element] * (counter[element] - 1) // 2

# print(counter[element])

print(match_cnt)

发表于 2025-10-21 11:46:30 回复(0)

精致的熊熊在努力存钱

n = int(input())

li = list(map(int,input().split()))

result = 0

li_new = [li[x]-x-1 for x in range(n)]

dic = {}

for i in li_new:

if i in dic.keys():

dic[i] += 1

else:

dic[i] = 1

for j in dic.values():

result += j*(j-1)/2

print(int(result))

发表于 2025-10-03 15:35:47 回复(0)

高兴0615

from collections import defaultdict

import sys

import math

n = int(input())

num_list = list(map(int, input().split()))

diff_dict = defaultdict(int)

for i in range(n):

diff = num_list[i] - i

diff_dict[diff] += 1

res = 0

for diff in diff_dict:

if diff_dict[diff] != 1:

res += (math.factorial(diff_dict[diff]) / (2 * math.factorial((diff_dict[diff]-2))))

print(int(res))

发表于 2025-09-20 17:00:07 回复(0)

Python3

xin202309

import sys

for line in sys.stdin:

a = line.split()

an=list(map(int,a))

vdict={}

counts=0

for i in range(len(an)):

v=an[i]-i

if v not in vdict:

vdict[v]=1

else:

counts+=vdict[v]

vdict[v]+=1

print(counts)

发表于 2025-09-14 21:20:16 回复(0)

Python3

忧伤的双曲线

n = int(input())

a = list(map(int,input().split()))

for i in range(n):

a[i] = a[i]-i

dic = {}

count = 0

for i in range(n):

if a[i] not in dic.keys():

dic[a[i]] = 1

else:

count += dic[a[i]]

dic[a[i]] += 1

print(count)

发表于 2025-08-26 15:23:32 回复(0)

学习小生

n = int(input())

arr = list(map(int, input().split()))

# 用字典统计每个差值出现的次数

diff_count = {}

for i in range(n):

diff = arr[i] - i

# 如果差值已在字典中，次数加1；否则初始化为1

diff_count[diff] = diff_count.get(diff, 0) + 1

num = 0

# 遍历字典中的次数，计算组合数并累加

for count in diff_count.values():

num += count * (count - 1) // 2

print(num)

发表于 2025-08-22 21:35:38 回复(0)

Python3

牛客847294653号

n = int(input())

a = list(map(int, input().strip().split()))

# 计算每个元素的"值减下标"

diff = [a[i] - i for i in range(n)]

# 统计相同差值的出现次数

count_map = {}

for val in diff:

count_map[val] = count_map.get(val, 0) + 1

# 计算谐距下标对数量

pairs = 0

for count in count_map.values():

# 如果有k个元素有相同的"值减下标"，则可以形成C(k,2)对

if count > 1:

pairs += count * (count - 1) // 2

print(pairs)

发表于 2025-08-22 10:33:14 回复(0)

Sen🍓🍀

转为 a[i] - i == a[j] - j
对 (a[i] - i) 计数

发表于 2025-07-10 21:02:34 回复(0)

提交观点

问题信息

排序

难度：

18条回答 101收藏 492浏览

谐距下标对

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题