有个物品,每个物品有个属性,第件物品的第个属性用一个正整数表示记为,两个不同的物品被称为是完美对的当且仅当,求完美对的个数。
进阶:时间复杂度,空间复杂度
import collections def ans(data): res = 0 hash_map = collections.defaultdict(int) for i in range(len(data)): diff = [] for j in range(1,len(data[0])): diff.append(data[i][j] - data[i][0]) str_1 = " ".join(str(id) for id in diff) str_2 = " ".join(str(-id) for id in diff) res += hash_map[str_2] hash_map[str_1] += 1 return res if __name__ == "__main__": num = list(map(int,input().split())) m = num[0] data = [] for i in range(m): data.append(list(map(int,input().split()))) print(ans(data))
def count(n, k, a_list): cnt = 0 delta_map = dict() for i in range(n): delta_list = [] for m in range(k-1): delta_list.append(a_list[i][m+1] - a_list[i][0]) p_str = ' '.join([str(j) for j in delta_list]) n_str = ' '.join([str(-j) for j in delta_list]) if delta_map.get(n_str): cnt += delta_map.get(n_str) if delta_map.get(p_str): delta_map[p_str] += 1 else: delta_map[p_str] = 1 return cnt