哈希算法题目：最长和谐子序列 题目描述： 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现在给定一个整数数组，你需要找到所有可能的和谐子序列中最长的长度。注意，和谐子序列要求元素可以是任意顺序，但必须由数组中的元素组成，且最长的和谐子序列指的是包含元素个数最多的那个。 解题过程： 让我们通过一个例子来理解：给定数组 [ 1,3,2,2,5,2,3,7]，最长的和谐子序列是 [ 3,2,2,2,3 ]，长度为5。 步骤1：理解和谐子序列的本质 和谐子序列由两个相差1的整数组成。例如，如果序列中包含x和x+1，那么由所有x和x+1组成的子序列就是和谐的。我们的目标是找到这样的x，使得数组中x和x+1的出现次数之和最大。 步骤2：使用哈希表统计频率 我们可以通过哈希表（字典）来统计每个数字出现的频率。遍历数组，对于每个数字，在哈希表中记录其出现次数。 对于例子 [ 1,3,2,2,5,2,3,7 ]： 数字1出现1次 数字2出现3次 数字3出现2次 数字5出现1次 数字7出现1次 哈希表：{1:1, 3:2, 2:3, 5:1, 7:1} 步骤3：寻找相邻数字对 接下来，我们遍历哈希表中的键（数字）。对于每个数字x，检查x+1是否也存在于哈希表中。如果存在，那么计算 count(x) + count(x+1) ，这个和就是一个候选的和谐子序列长度。 在我们的例子中： x=1: x+1=2存在，长度=1+3=4 x=2: x+1=3存在，长度=3+2=5 x=3: x+1=4不存在，跳过 x=5: x+1=6不存在，跳过 x=7: x+1=8不存在，跳过 步骤4：处理特殊情况 如果数组中所有数字都相同（例如[ 1,1,1,1 ]），那么不存在相差1的数字对，最长和谐子序列长度为0。因为和谐子序列至少需要两个不同的数字。 步骤5：算法实现 创建一个空哈希表frequency_ map 遍历数组，统计每个数字的出现频率 初始化max_ length = 0 遍历frequency_ map中的每个数字num： 如果num+1在frequency_ map中： 当前长度 = frequency_ map[ num] + frequency_ map[ num+1 ] 如果当前长度 > max_ length，则更新max_ length 返回max_ length 时间复杂度：O(n)，其中n是数组长度。我们只需要遍历数组一次统计频率，再遍历哈希表一次检查相邻数字。 空间复杂度：O(n)，用于存储哈希表。 这个算法高效地利用了哈希表来统计频率和快速查找相邻数字，避免了暴力枚举所有子序列的高复杂度。