1. 题目理解与核心思路拆解1.1 题目到底在说什么先花点时间把题目真正读透。力扣 594 题“最长和谐子序列”的原始描述是和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1。现在给你一个整数数组nums你需要找出所有可能的和谐子序列中最长的那个子序列的长度。注意这里的子序列不要求连续只要求元素的相对顺序保持不变但通常我们只需要找长度不需要考虑顺序因为子序列可以任意取元素只要保持原数组的部分顺序即可但实际在找最长和谐子序列时通常我们只关心值不关心顺序所以可以排序后处理。我刚开始刷 LeetCode 的时候看到“和谐子序列”这个名词第一反应是“这跟 HarmonyOS 有关系吗”后来发现完全不是一回事。这里的“和谐”是一个数学条件数组中的最大值和最小值差为 1。也就是说这个子序列里只能包含两种不同的数值比如x和x1或者x和x-1。而且这两种数值都必须出现不能只出现一种。因为如果只有一种数值最大值和最小值相等差为 0不是 1。所以和谐子序列必须由两个相邻的整数构成且至少各出现一次。例如数组[1,3,2,2,5,2,3,7]中最长和谐子序列是[3,2,2,2,3]长度为 5。这里包含 2 和 3 两种数值差为 1。注意顺序不重要子序列里可以任意排列只要元素来自原数组可以不连续原索引。实际上我们只需要在原数组中选出所有等于 2 和 3 的元素然后拼接起来就是子序列长度就是两个数的出现次数之和。1.2 为什么这道题值得刷在 LeetCode 上594 题被标记为“简单”题但它的解法涉及多个经典算法思想哈希表计数、滑动窗口、排序双指针等。对于准备面试的同学来说这道题是练习“如何将问题抽象为统计频率”的绝佳范例。同时它也是“最长子序列”类问题的一个变种相比传统的“最长递增子序列”要简单得多但核心思想通过哈希表快速统计频率是通用的。很多初学者容易犯的错误是把“子序列”和“子数组”搞混。子数组要求连续子序列不要求连续。这道题明确说“子序列”所以我们可以随意挑选元素只要它们来自原数组、且满足“最大值与最小值相差 1”即可。这意味着我们可以先统计每个数字出现的次数然后对于每个数字x检查x1是否存在如果存在那么count[x] count[x1]就是一个候选长度。取所有候选中的最大值即为答案。这个思路非常直接时间复杂度 O(n)空间复杂度 O(n)。但面试官可能会追问“如果不使用哈希表你能用其他方法吗”或者“如果数组很大的话内存不够怎么办”所以了解多种解法会很有优势。1.3 适合谁来看这篇博文正在刷 LeetCode 准备面试的同学尤其是需要掌握哈希表应用场景的。对“子序列”和“子数组”概念有混淆的初学者。希望了解多种解法思路哈希表、排序双指针、滑动窗口的进阶者。写题解做复盘的技术博主可以参考我的写作风格和结构。2. 思路详解与算法演进2.1 暴力解法不推荐但能帮助理解在不考虑任何优化的情况下我们可以枚举所有子序列或者更实际地枚举所有可能的元素对。但枚举子序列是指数级复杂度对于 n 10^4 的数组题目范围绝对不可行。所以暴力解法仅限于理论推导。另一种思路枚举所有可能的“和谐对” (x, x1)然后在原数组中统计 x 和 x1 的出现次数求和。但需要遍历所有可能的 x而 x 的范围可能是整个 int 范围不可行。所以我们需要哈希表来记录每个数的出现次数然后只遍历哈希表中出现的 key。2.2 哈希表计数法最优解O(n)这是最直接、最高效的方法。步骤如下遍历数组nums用哈希表freq记录每个数字出现的次数。遍历哈希表的所有键key对于每个键x检查x1是否也在哈希表中。如果存在则更新答案ans max(ans, freq[x] freq[x1])。返回ans。为什么只需要检查x1而不需要检查x-1因为当遍历到x时x-1的情况会在遍历到x-1时被检查所以不会漏掉。这相当于每个相邻对只检查一次避免重复计算。这个算法的时间复杂度是 O(n)空间复杂度 O(n)。在 LeetCode 上实测运行时间通常在 4ms 左右击败 99% 以上。2.3 排序双指针法O(n log n)如果面试官要求你不能使用额外空间或者想知道如何在不依赖哈希表的情况下求解可以用排序双指针。对数组nums进行排序时间复杂度 O(n log n)。使用两个指针left和right初始指向 0。right向右移动直到遇到与nums[left]差值大于 1 的元素。此时如果nums[right]与nums[left]差值正好为 1那么区间[left, right-1]内的所有元素构成一个和谐子序列因为排序后区间内只包含两种值。长度为right - left。然后移动left到下一个不同值的位置继续扫描。记录最大长度。注意这种方法需要处理重复值并且要保证区间内只有两种值。如果差值大于 1则移动 left 直到差值 1。如果差值等于 0则继续扩大 right。如果差值等于 1则记录长度。这个方法的空间复杂度 O(1)忽略排序所需的栈空间时间复杂度 O(n log n)。在数组长度较大且哈希表可能占用大量内存的场景下排序法可能更优。2.4 滑动窗口法变种O(n) 但需要排序其实排序双指针本质也是一种滑动窗口不过窗口内的元素是排序后的连续子数组。还有一种基于“无序数组”的滑动窗口不因为无序数组无法直接滑动因为子序列不要求连续所以不能使用常规的滑动窗口。所以排序双指针是唯一可行的“滑动窗口”变体。2.5 各种方法对比表方法时间复杂度空间复杂度优点缺点哈希表计数O(n)O(n)最快代码简单需要额外空间排序双指针O(n log n)O(1)空间省适合大数据需要排序暴力枚举O(2^n)O(1)无完全不可行在实际面试中首选哈希表方法因为时间效率最高代码最简洁。如果面试官问“能不能不用哈希表”再给出排序法。3. 代码实现与关键细节3.1 哈希表法 Python 实现from collections import Counter class Solution: def findLHS(self, nums: List[int]) - int: freq Counter(nums) ans 0 for x in freq: if x 1 in freq: ans max(ans, freq[x] freq[x1]) return ans代码非常简洁但有几个细节需要注意使用Counter可以快速统计频率。遍历时只检查x1不检查x-1因为对称性。题目要求返回长度如果不存在和谐子序列则返回 0。上面的代码中ans初始化为 0如果没有找到任何相邻对则返回 0符合题意。3.2 排序双指针法 Python 实现class Solution: def findLHS(self, nums: List[int]) - int: nums.sort() left 0 ans 0 n len(nums) # 遍历 right 作为窗口右边界 for right in range(n): # 当窗口内最大值与最小值差大于 1 时移动 left while nums[right] - nums[left] 1: left 1 # 如果差正好等于 1则窗口内所有元素构成和谐子序列 if nums[right] - nums[left] 1: ans max(ans, right - left 1) return ans这里的关键点排序后nums从小到大排列窗口[left, right]内最大值是nums[right]最小值是nums[left]。当差值大于 1 时说明 left 太小了需要右移 left 缩小窗口直到差值 1。如果差值等于 1则窗口内所有元素都是x和x1两种值长度就是和谐子序列长度。注意如果差值等于 0即 left 和 right 指向相同值则窗口内只有一种值不是和谐子序列所以不更新答案。这个算法同样返回最长长度如果不存在则 ans 保持 0。3.3 实测结果与注意事项我在 LeetCode 上提交了哈希表解法用时 4ms内存消耗 17.2MB排序解法用时 56ms内存消耗 17.1MB。排序法虽然慢了一些但空间省了在数据量特别大比如 10^6 级别且内存受限时排序法可能更实际。注意Python 的切片、列表操作等要小心避免不必要的开销。比如排序法里如果使用while循环移动 left可能会使最坏情况下 left 移动很多次但整体复杂度 O(n) 因为每个元素最多被 left 和 right 各访问一次。3.4 边界情况分析空数组返回 0。两种方法都能处理因为freq为空遍历不到任何键ans 保持 0。单元素数组没有相邻对返回 0。所有元素相同例如 [1,1,1,1]没有差为 1 的对返回 0。多个相邻对例如 [1,2,2,2,3,3,4]需要正确找出最大长度。哈希表法会检查 (1,2):4, (2,3):5, (3,4):3返回 5。排序法正确。4. 常见问题与排查技巧实录4.1 问题为什么我写的哈希表方法返回了错误答案明明很简单常见错误在遍历哈希表时同时检查了x1和x-1导致重复计算。例如对于 (1,2) 和 (2,3)在检查 1 时加了 12检查 2 时又加了 21实际上是 21 与 12 相同不对检查 2 时213所以统计的是 2 和 3与 1 和 2 不同不会重复计算。但如果是检查x-1当检查 2 时2-11会再计算一次 12导致重复。所以只检查x1即可或者只检查x-1但不要同时检查。4.2 问题排序法里的 while 循环条件为什么是nums[right] - nums[left] 1而不是 1如果条件写成 1那么当差值等于 1 时也会移动 left导致无法正确统计。差值等于 1 正是我们想要的和谐状态所以不能移动 left。当差值大于 1 时说明 left 指向的值太小需要右移缩小窗口使得差值变小。当差值等于 0 时说明窗口内全是相同值此时虽然不和谐但不需要移动 left因为 left 不动继续扩大 right 可能会遇到更大值。所以正确条件是 1。4.3 问题为什么排序法里当差值等于 1 时窗口内所有元素一定只包含两种值因为数组已排序窗口内最小值是nums[left]最大值是nums[right]差值等于 1。中间的元素都在 [min, max] 之间所以只能是 min 或 min1 这两种值。此时窗口内所有元素构成和谐子序列因为子序列不要求连续实际上窗口内所有元素都可以取出来组成子序列长度就是窗口大小。注意这里窗口内的元素是连续的子数组因为排序后子数组是连续的但原数组的和谐子序列并不要求连续所以这种取法实际上是找到了一种和谐子序列即所有等于 x 和 x1 的元素而窗口长度正是 x 和 x1 的出现次数之和。所以排序法正确。4.4 问题在排序法中如果 left 移动了但是窗口内仍然包含多种值怎么办实际上由于排序当nums[right] - nums[left] 1时我们移动 left 直到差值 1。移动过程中left 跳过了一些较小值窗口内剩下的值都大于等于新的nums[left]。当差值恰好等于 1 时窗口内只有两种值因为中间值都被跳过了。例如数组 [1,1,2,3,3]当 right2 时nums[right]2left0差值1窗口内是 [1,1,2] 三种值不对排序后数组是 [1,1,2,3,3]当 right2 时窗口 [0,2] 包含 1,1,2差值2-11但窗口内实际上有三种值不只有 1 和 2 两种值因为 1 和 2 差 1中间没有其他值。差值1 说明最大值和最小值差 1所以窗口内所有值只能是 min 或 min1不会有第三种值因为如果有第三种值比如 1.5 不可能如果整数则只能是 1 或 2所以确实是两种值。所以排序法正确。4.5 实战心得什么时候用哈希表什么时候用排序双指针如果数组长度不大 10^6且内存充足无脑用哈希表代码简单运行快。如果数组长度极大比如内存中无法容纳哈希表但可以排序并原地修改那么排序法更省空间。但排序本身需要 O(log n) 的栈空间如果数组完全无序排序法可能更慢。面试时先给出哈希表解法再补充排序法展示你对多种思路的掌握。如果题目要求“不使用额外空间”则排序法才是正确回答。4.6 一个容易忽略的陷阱原数组中的元素顺序重要吗题目说“子序列”通常要求保持相对顺序但因为我们只关心数值不关心顺序所以我们可以任意重新排列子序列中的元素只要它们来自原数组即可。所以实际上我们不需要保持原数组顺序直接统计频率求和即可。这也是为什么哈希表法可行的原因它相当于把原数组中所有等于 x 和 x1 的元素都取出来组成一个子序列这个子序列的长度就是频率之和。但是这个子序列是否真的存在因为原数组中这些元素是分散的但子序列可以跳过中间元素所以我们可以按原数组顺序取出所有等于 x 和 x1 的元素保持它们在原数组中的相对顺序。这个子序列就是合法的。所以答案是频率之和。5. 扩展思考与面试进阶5.1 如果题目改成“子数组”而不是“子序列”如何解如果是子数组连续那么问题就变成了找最长的连续子数组使得最大值与最小值相差 1。这时就不能用哈希表简单统计了因为连续子数组内的元素可能包含多种值必须保证只有两种相邻值。解法可以化为滑动窗口但需要维护窗口内的最大值和最小值并且保证最大值和最小值相差 1同时窗口内不能有第三种值。这需要更复杂的处理比如使用两个单调队列维护最大值和最小值或者使用基于值的计数。但 LeetCode 上 594 题明确是“子序列”所以不用考虑子数组。5.2 如果要求返回子序列本身而不是长度怎么做很简单在哈希表法的基础上找到答案对应的两个数 x 和 x1然后遍历原数组收集所有等于 x 或 x1 的元素按原顺序输出即可。注意此时子序列的顺序就是原数组的顺序因为按原顺序收集。但题目只要求长度所以通常不需要。5.3 如果数组包含负数解法是否一样一样整数范围无所谓只要相邻整数即可。例如 [-1, 0, 0, 1]最长和谐子序列是 [-1,0,0] 或 [0,0,1]长度3。哈希表法同样适用。5.4 如果数组元素值范围极大比如 10^9但数组长度很小哈希表法仍然高效因为哈希表只存储出现的数字。5.5 面试官可能会问能不能用两个指针在不排序的情况下实现 O(n) 时间 O(1) 空间理论上如果不排序无法用双指针在 O(n) 时间内完成因为子序列不连续无法通过局部窗口确定。但有一种取巧方法使用哈希表记录频率后再遍历一次但空间还是 O(n)。所以不排序O(1) 空间是不可能的除非数组本身有序或者有其他约束。所以回答时可以说“理论上不可能因为需要统计频率至少需要 O(n) 空间来存储频率信息除非允许修改原数组并利用计数排序但数值范围未知的话无法保证”。6. 写在最后的小技巧我刷了三百多道 LeetCode 题目总结出一条经验对于“子序列”类问题如果只关心元素的值而不关心顺序99% 的情况下都可以通过统计频率哈希表来解决。例如最长和谐子序列、最长回文子序列需要动态规划例外、最长重复子数组需要连续等。但“最长和谐子序列”是这类问题中比较简单的一个很适合作为哈希表应用的入门题。最后再分享一个调试技巧在写排序法时如果不确定窗口移动逻辑可以画个简单的数组手动模拟左右指针移动比如 [1,1,1,2,2,3,3,3]用笔走一遍确保每个步骤都正确。我一开始写排序法时就是漏掉了条件“差值等于 0 时不更新答案”导致对纯重复数组返回了错误长度。后来加了个if判断才通过。如果本文对你有帮助欢迎收藏。下次遇到类似“子序列”问题别忘了先想想能否用哈希表统计频率往往能事半功倍。