难度: Easy
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
示例 1：
输入：nums = [1,3,2,2,5,2,3,7] 输出：5 解释：最长的和谐子序列是 [3,2,2,2,3]
示例 2：
输入：nums = [1,2,3,4] 输出：2
示例 3：
输入：nums = [1,1,1,1] 输出：0
提示：
1 <= nums.length <= 2 * 104-109 <= nums[i] <= 109运行时间: 240 ms
内存: 17.8 MB
class Solution:
def findLHS(self, nums: List[int]) -> int:
cnt = Counter(nums)
ret = 0
for key, val in cnt.items():
if key + 1 not in cnt:
continue
ret = max(ret, val + cnt[key + 1])
return ret
这个题解使用了哈希表的思路。首先用 Counter 统计数组中每个数字出现的次数，然后遍历哈希表中的每个键值对。对于每个键 key，如果 key+1 也在哈希表中，就计算 key 和 key+1 出现次数之和，并更新结果 ret 为 ret 和这个和中较大的那个。最后返回 ret 即可。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findLHS(self, nums: List[int]) -> int:
# 用 Counter 统计每个数字出现的次数
cnt = Counter(nums)
ret = 0
for key, val in cnt.items():
# 如果 key+1 不在哈希表中，继续循环
if key + 1 not in cnt:
continue
# 更新结果为 ret 和 key 与 key+1 出现次数之和中较大的那个
ret = max(ret, val + cnt[key + 1])
return ret
哈希表被选择用于解决这个问题，因为它能以高效的方式存储和查找键值对，其中键是元素值，而值是该元素在数组中出现的次数。在这个问题中，我们需要频繁地查询某个数字及其相邻数字是否存在，以及它们的出现频次。使用哈希表，我们可以实现对这些信息的快速访问（平均时间复杂度为O(1)），这是因为哈希表提供了非常快的查找、插入和删除操作。总之，哈希表在这里主要起到了快速统计和检索数据的作用，从而允许我们高效地计算和谐子序列的长度。
在题解中，只检查key+1而不是key-1的原因是为了避免重复计算。由于和谐子序列由数对 'key' 和 'key+1' 组成，如果我们同时检查 'key-1'，那么每对相邻的数会被计算两次（一次作为 'key' 和 'key+1'，一次作为 'key-1' 和 'key'）。通过只查看 'key+1'，我们可以确保每一对和谐子序列只被计算一次，从而提高算法的效率和避免不必要的重复计算。
如果哈希表中的键值对非常多，确实会影响算法的性能。首先，哈希表的空间复杂度会增加，需要更多的内存来存储这些键值对。其次，虽然平均情况下哈希表的查找、插入和删除操作的时间复杂度为O(1)，但在最坏情况下，这些操作的时间复杂度可能退化为O(n)，尤其是在哈希冲突较多的情况下。此外，遍历哈希表的时间复杂度为O(n)，其中n是键值对的数量，因此如果键值对非常多，遍历操作的开销也会增大。总之，键值对数量的增加，会在空间复杂度、时间复杂度和操作效率上带来影响。