题解 | 谐距下标对

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int a[]=new int[n];
		int b[]=new int[n];
//		可以把a[j]-a[i]=j-i转化为a[j]-j=a[i]-i
		for (int i = 0; i < a.length; i++) {
			a[i]=scanner.nextInt();
			b[i]=a[i]-i;
		}
		HashMap<Integer, Integer> map=new HashMap<>();
		for (int i = 0; i < b.length; i++) {
			map.put(b[i], map.getOrDefault(b[i], 0)+1);
		}
		long count=0;
		for(Map.Entry<Integer, Integer> x:map.entrySet()) {
			long k=x.getValue();
			if(k==1)continue;
			//这里其实就是从k个数中取2个数，一个组合问题
			count+=k*(k-1)/2;
		}
		
//		下面的办法时间复杂度是O（n^2），会超时
//		int count=0;
//		for (int i = 0; i < a.length; i++) {
//			for (int j = i+1; j < a.length; j++) {
//				if(a[j]-a[i]==j-i) {
//					count++;
//				}
//				
//			}
//		}
		System.out.println(count);

	}

}

这题直接使用双重for循环进行遍历会超时，因为时间复杂度为n^2，我们需要进行优化。根据题目意思，a[j]-a[i]=j-i，可以转换成a[i]-i=a[j]-j，这样我们就可以使用一个数组来装元素与索引的差值，再使用Map去统计每一种元素出现的次数，如果超过1，那么就进行组合运算，从k个中选出两个