当前位置：首页 > article >正文

LeetCode题练习与总结：最长和谐子序列--594

article 2025/1/31 13:00:34

一、题目描述

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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

二、解题思路

首先我们需要统计数组中每个数字出现的次数，可以使用哈希表来实现。
遍历哈希表，对于每个键值对，检查是否存在键值加一的情况。如果存在，那么这两个键值对可以构成和谐子序列。
计算这两个键值对对应的值的和，即为当前和谐子序列的长度。
更新最长和谐子序列的长度。
返回最长和谐子序列的长度。

三、具体代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        int longest = 0;
        for (int key : count.keySet()) {
            if (count.containsKey(key + 1)) {
                longest = Math.max(longest, count.get(key) + count.get(key + 1));
            }
        }
        
        return longest;
    }
}

这段代码首先通过一个for循环统计数组中每个数字出现的次数，然后通过另一个for循环遍历哈希表，寻找和谐子序列并计算其长度，最后返回最长和谐子序列的长度。

四、时间复杂度和空间复杂度

1. 时间复杂度

统计数组中每个数字出现的次数：我们遍历了整个数组一次，因此这一步的时间复杂度是 O(n)，其中 n 是数组的长度。
遍历哈希表并寻找和谐子序列：在最坏的情况下，我们需要遍历整个哈希表，哈希表中可能包含与数组长度相同数量的键值对，因此这一步的时间复杂度也是 O(n)。

综合以上两步，总的时间复杂度是 O(n) + O(n) = O(n)，即线性时间复杂度。

2. 空间复杂度

哈希表存储数组中每个数字出现的次数：在最坏的情况下，如果数组中的所有数字都是不同的，那么哈希表的大小将与数组的长度相同，因此空间复杂度是 O(n)。

综上所述，代码的时间复杂度是 O(n)，空间复杂度也是 O(n)。这里的 n 是输入数组的长度。

五、总结知识点

哈希表（HashMap）：
- 使用 HashMap 来存储数组中每个数字出现的次数。
- put 方法用于在哈希表中插入键值对。
- getOrDefault 方法用于获取键对应的值，如果键不存在，则返回默认值。
增强型 for 循环：
- 使用增强型 for 循环来遍历数组 nums 和哈希表的键集 count.keySet()。
条件判断：
- 使用 if 语句来检查哈希表中是否存在当前键值加一的情况。
数学函数：
- 使用 Math.max 函数来更新最长和谐子序列的长度。
数组的遍历：
- 通过 for 循环对数组进行遍历。
键值对操作：
- 通过 containsKey 方法检查哈希表中是否存在特定的键。
默认值处理：
- 使用 getOrDefault 方法处理哈希表中不存在的键，并为其设置默认值。
整型变量操作：
- 对整型变量进行增加和比较操作。
方法返回值：
- 使用 return 语句返回计算得到的最长和谐子序列的长度。