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
解释：最长的和谐子序列有 [1,2]、[2,3] 和 [3,4]，它们的长度都是 2。

示例 3：

输入：nums = [1,1,1,1]
输出：0
解释：不存在和谐子序列。

约束条件：

  • 1 <= nums.length <= 2 * 10^4
  • -10^9 <= nums[i] <= 10^9

解题思路

解题思路

要找到最长的和谐子序列，关键在于理解和谐数组的定义：数组中的最大值和最小值的差值恰好为 1。这意味着和谐子序列只能包含两种相邻的数值，比如只包含 x 和 x+1。

方法分析：

  1. 哈希表法（推荐）：统计每个数字的出现次数，然后对于每个数字 x，检查 x+1 是否存在，如果存在则计算 count(x) + count(x+1) 的长度。这种方法时间复杂度为 O(n)，空间复杂度为 O(n)。

  2. 排序法：先对数组排序，然后使用双指针扫描相邻的相同元素，计算差值为 1 的两个连续段的长度之和。时间复杂度为 O(n log n)，空间复杂度为 O(1)。

哈希表法更高效，因为它只需要一次遍历就能解决问题。核心思想是：对于任意数字 x，如果 x+1 也存在于数组中，那么包含 x 和 x+1 的子序列就是一个和谐子序列，其长度为这两个数字的出现次数之和。

我们遍历所有可能的数字对 (x, x+1)，找到能组成最长和谐子序列的那一对。

代码实现

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        int maxLen = 0;
        for (auto& [num, freq] : count) {
            if (count.count(num + 1)) {
                maxLen = max(maxLen, freq + count[num + 1]);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        from collections import Counter
        
        count = Counter(nums)
        max_len = 0
        
        for num in count:
            if num + 1 in count:
                max_len = max(max_len, count[num] + count[num + 1])
        
        return max_len

public class Solution {
    public int FindLHS(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        int maxLen = 0;
        foreach (var kvp in count) {
            int num = kvp.Key;
            int freq = kvp.Value;
            if (count.ContainsKey(num + 1)) {
                maxLen = Math.Max(maxLen, freq + count[num + 1]);
            }
        }
        
        return maxLen;
    }
}

var findLHS = function(nums) {
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    let maxLen = 0;
    for (const [num, freq] of count) {
        if (count.has(num + 1)) {
            maxLen = Math.max(maxLen, freq + count.get(num + 1));
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表法排序法
时间复杂度O(n)O(n log n)
空间复杂度O(n)O(1)

其中 n 为数组长度。推荐使用哈希表法，因为其时间复杂度更优。