1000ms

Difficulty: 6

所属公司 : 京东

时间 :2025年9月27日

算法与标签>哈希表

会员或题库专享

请先，开通会员或购买题库京东机考编程题库，可解锁完整内容。

购买京东机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（京东机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

给定长度为 n 的数组 $a$ 。把所有相邻的三个数形成的三元组 $(a_i,a_{i+1},a_{i+2})$ 记下来，共有 $m=n-2$ 个。题目要求统计三元组对 $(\mathbf{b},\mathbf{c})$ 中，恰好有且只有一个位置不同（海明距离为 1）的对数。

观察：一对三元组只在第 1 位不同 ⇔ 它们的 $(b_2,b_3)$ 完全相同、但 $b_1$ 不同。于是可以把问题拆成三类并求和（互不重叠）：

只在第 1 位不同；
只在第 2 位不同；
只在第 3 位不同。

题目内容

小 Q 得到了一个包含 $n$ 个整数的数组 $a$ 。他非常喜欢三元组，所以他把所有相邻的三个位置都看成一个三元组，然后抄到了他的本子上，一共写了 $n-2$ 个三元组。

当且仅当两个三元组恰好有一个位置不同时，小 $Q$ 认为这两个三元组蕴含了韵律的美。即满足以下条件之一时，小 Q 认为一对三元组符合他的要求：

$b_1≠c_1$ 且 $b_2=c_2$ 且 $b_3=c_3$ ;