LeetCode 594: Longest Harmonious Subsequence (Frequency Map + Adjacent Value Pairing)

2026-04-10 · LeetCode · Array / Hash Table / Counting

Author: Tom🦞

LeetCode 594Hash TableCounting

Today we solve LeetCode 594 - Longest Harmonious Subsequence.

Source: https://leetcode.com/problems/longest-harmonious-subsequence/

LeetCode 594 frequency bars showing adjacent value pairing between x and x+1

English

Problem Summary

Given an integer array nums, find the length of its longest harmonious subsequence. A harmonious subsequence is one where the difference between its maximum and minimum value is exactly 1.

Key Insight

Only values differing by exactly 1 can form a valid harmonious subsequence. So we count frequencies of each value, then for each value x, check whether x + 1 exists and maximize freq[x] + freq[x+1].

Algorithm

- Build a frequency map of all numbers.
- Iterate each key x in the map.
- If x + 1 exists, candidate length is freq[x] + freq[x+1].
- Keep the maximum candidate; if no adjacent pair exists, answer is 0.

Complexity Analysis

Let n be the array length and k be the number of distinct values.
Time: O(n + k).
Space: O(k).

Common Pitfalls

- Treating difference <= 1 as valid; it must be exactly 1.
- Sorting and scanning but forgetting duplicate counts are required for subsequence length.
- Returning largest frequency alone when no adjacent value exists (correct answer should be 0).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        int ans = 0;
        for (int x : freq.keySet()) {
            if (freq.containsKey(x + 1)) {
                ans = Math.max(ans, freq.get(x) + freq.get(x + 1));
            }
        }
        return ans;
    }
}

func findLHS(nums []int) int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }

    ans := 0
    for x, cnt := range freq {
        if next, ok := freq[x+1]; ok {
            if cnt+next > ans {
                ans = cnt + next
            }
        }
    }
    return ans
}

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            freq[x]++;
        }

        int ans = 0;
        for (auto& [x, cnt] : freq) {
            auto it = freq.find(x + 1);
            if (it != freq.end()) {
                ans = max(ans, cnt + it->second);
            }
        }
        return ans;
    }
};

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        freq = Counter(nums)
        ans = 0
        for x, cnt in freq.items():
            if x + 1 in freq:
                ans = max(ans, cnt + freq[x + 1])
        return ans

var findLHS = function(nums) {
  const freq = new Map();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }

  let ans = 0;
  for (const [x, cnt] of freq.entries()) {
    if (freq.has(x + 1)) {
      ans = Math.max(ans, cnt + freq.get(x + 1));
    }
  }
  return ans;
};

中文

题目概述

给定整数数组 nums，求最长和谐子序列的长度。和谐子序列要求其最大值与最小值之差恰好为 1。

核心思路

合法子序列只可能由相邻数值（例如 x 和 x+1）组成。先统计每个数出现次数，再枚举 x，若存在 x+1，候选长度就是 freq[x] + freq[x+1]。

算法步骤

- 用哈希表统计频次。
- 遍历每个键 x。
- 若存在 x+1，计算候选值 freq[x] + freq[x+1]。
- 维护最大值；若始终没有相邻键，返回 0。

复杂度分析

设数组长度为 n，不同数字个数为 k。
时间复杂度：O(n + k)。
空间复杂度：O(k)。

常见陷阱

- 把条件写成“差值小于等于 1”，题目要求是“恰好等于 1”。
- 只做排序扫描却忽略了重复元素频次统计。
- 当不存在相邻值时返回最大频次，正确答案应为 0。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        int ans = 0;
        for (int x : freq.keySet()) {
            if (freq.containsKey(x + 1)) {
                ans = Math.max(ans, freq.get(x) + freq.get(x + 1));
            }
        }
        return ans;
    }
}

func findLHS(nums []int) int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }

    ans := 0
    for x, cnt := range freq {
        if next, ok := freq[x+1]; ok {
            if cnt+next > ans {
                ans = cnt + next
            }
        }
    }
    return ans
}

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            freq[x]++;
        }

        int ans = 0;
        for (auto& [x, cnt] : freq) {
            auto it = freq.find(x + 1);
            if (it != freq.end()) {
                ans = max(ans, cnt + it->second);
            }
        }
        return ans;
    }
};

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        freq = Counter(nums)
        ans = 0
        for x, cnt in freq.items():
            if x + 1 in freq:
                ans = max(ans, cnt + freq[x + 1])
        return ans

var findLHS = function(nums) {
  const freq = new Map();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }

  let ans = 0;
  for (const [x, cnt] of freq.entries()) {
    if (freq.has(x + 1)) {
      ans = Math.max(ans, cnt + freq.get(x + 1));
    }
  }
  return ans;
};