2016 Silver December p2

题目

给出 N 个城市（1 ≤ N ≤ 200000），每个城市有自己的名字和长度为两个字母的代号（可能会重复）。若两个城市是一对 special pair ，则这两个城市的名称的前两个字母都是对方的代号。找出这 N 个城市中有多少对 special pair

思路

将城市的前两个字母和代号分别装进一个长度为 2 的元组的两个房间，并将每个这样的元组装进 hashmap 中，其中每个元组作为 key，出现的次数作为 value。遍历 hashmap，将当前的元组的前后两格互换，若 hashmap 中有与新元组相同的 key，则 count 加上当前的 valve 与新 value 的积

复杂度分析

遍历 hashmap 的复杂度为 O(N)，在 hashmap 中查找 key 的复杂度为 O(1)，总复杂度为 O(N)。N 最大为 200000，不会超时