一、问题描述

有 n _n_个物品，每个物品有 k _k_个属性，第 i _i_件物品的第 j j_个属性用一个正整数表示记为ai,j_a**i,j，两个不同的物品 i,j i,j_被称为是完美对的当且仅当ai,1+aj,1=ai,2+aj,2=⋯=ai,k+aj,k_a**i,1+a**j,1=a**i,2+a**j,2=⋯=a**i,k+a**j,k，求完美对的个数。

输入例子：

5 3  
2 11 21  9,10;
19 10 1  -9,-9;
20 11 1  -9,-10;
6 15 24  9,9;
18 27 36 9,9;

输出例子：

3

满足条件的：

// 思路一： o(n*k)
// {2, 11, 21},{20, 11, 1}
// {19, 10, 1},{6, 15, 24}
// {19, 10, 1},{18, 27, 36}

二、方案一：暴力法

1、思路

暴力法是最直观的方法，通过二重循环遍历所有可能的二元组组合，然后检查它们的和是否等于目标值。

2、代码实现

func perfectPairs(n, k int, items [][]int) int {
	perfectPairs := 0
	sum := 0
	flag := false // 是否符合要求

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			flag = false
			sum = items[i][0] + items[j][0]
			for r := 1; r < k; r++ {
				if items[i][r]+items[j][r] != sum {
					flag = false
					break
				} else {
					flag = true
				}
			}
			if flag {
				perfectPairs += 1
			}
		}
	}

	return perfectPairs
}

3、复杂度分析

• 时间复杂度：O(n^3)，因为有3层循环。
• 空间复杂度：O(1)

三、方案二：哈希表

公式转换

已知 a1 + b1 = a2 + b2 = a3 + b3

a1-a2 = b2-b1 => a2-a1 = -(b2-b1)
a2-a3 = b3-b2 => a3-a2 = -(b3-b2)

5 3  
2 11 21  9,10
19 10 1  -9,-9
20 11 1  -9,-10
6 15 24  9,9
18 27 36 9,9

思路：

• 物品等同于一行数字，物品属性等同于行内元素值
• 针对每行数字，使用相邻数字之间的差值转换为字符串，构建当前行的模式字符串
• 使用哈希表记录每行数字对应的模式 key 出现的次数
• 检查哈希表中是否已经存在key2（即当前行的逆模式）。存在则表明之前已经有与当前行形成完美对, 更新计数器 perfectPairsCount

代码：

func perfectPairs(n, k int, nums [][]int) int {
	perfectPairsCount := 0
	diff := 0
	m := map[string]int{}

	for i := 0; i < n; i++ {
		key := "" // 模式
		key2 := "" // 逆模式
		for r := 1; r < k; r++ {
			diff = nums[i][r] - nums[i][r-1]
			key += strconv.Itoa(diff) + ","
			key2 += strconv.Itoa(-diff) + ","
		}
		// 之前出现过逆模式，则互为完美对
		if _, ok := m[key2]; ok {
			perfectPairsCount += m[key2]
		}
		// 记录当前模式对应的次数
		m[key] += 1
	}

	return perfectPairsCount
}