第 484 场周赛Q3——3805. 统计凯撒加密对数目

题目链接：3805. 统计凯撒加密对数目（中等）

算法原理：

解法：哈希表

215ms击败16.95%

时间复杂度O(N∗M)

时间长主要是因为使用了StringBuffer~

通过观察不难发现，其实只要两个字符串中各个字符相对于自己字符串的首字符的相对偏移量不变，那么这两个字符串就能通过若干次变化成为相同的字符串，那么我们就可以通过记录这个相对偏移量而规定成偏移量特征码，只要两个字符串的特征码相同，它们就能成为相同字符串

①用Map收集各个特征码出现的次数，由于题目要的是对数，需要两两成对，那么最终结果只需要加上该特征码能形成的对数即可，比如这个特征码出现c次，那么可以形成的对数就可以表示为c×(c-1)/2

②用数字记录偏移量，要记得+26再去%26，能避免负数还能自然的完成从‘z’到'a'的转换

③用StringBuffer记录特征码，为了防止1和12拼接在一起可能会造成11和2拼接的误差，所以中间再多拼接一个“，”

Java代码：

class Solution { public long countPairs(String[] words) { //存储偏移量特征码 Map<String,Integer> hash=new HashMap<>(); for(String s:words){ char ch=s.charAt(0); StringBuffer sb=new StringBuffer(); for(char c:s.toCharArray()){ int offset=(c-ch+26)%26; sb.append(offset).append(","); } hash.put(sb.toString(),hash.getOrDefault(sb.toString(),0)+1); } long ret=0; for(int count:hash.values()) ret+=(long)count*(count-1)/2; return ret; } }