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

一、题目描述

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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. 首先我们需要统计数组中每个数字出现的次数，可以使用哈希表来实现。
2. 遍历哈希表，对于每个键值对，检查是否存在键值加一的情况。如果存在，那么这两个键值对可以构成和谐子序列。
3. 计算这两个键值对对应的值的和，即为当前和谐子序列的长度。
4. 更新最长和谐子序列的长度。
5. 返回最长和谐子序列的长度。

三、具体代码

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 语句返回计算得到的最长和谐子序列的长度。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。