和谐子序列的定义
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1，也就是说我们需要找出比该元素大于或者相等的元素
LeetCode 题目：
给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度
题目示例：
输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
暴力枚举的思想很简单，也是我们常用的方法，就是双重遍历数组，第一层遍历是枚举数组中的每一个元素并且假设该元素是数组中最小的元素，第二层遍历是枚举元素与该数组中的每一个元素逐一比较，找出等于枚举元素或者比枚举元素大一的元素，统计出最终的元素个数。
1、解题代码
public static int findLHS(int[] nums) {
// 记录最大的和谐子序列长度
int res = 0;
// 第一层遍历，当前元素默认为最小的元素
for (int i = 0; i < nums.length; i++) {
// 当前元素最长的子序列长度
int count = 0;
// 第二层遍历，与数组中的每一个元素进行比较，找出 nums[i]+1 = nums[j] 或者 nums[i]==nums[j] 的元素个数
for (int j = 0; j < nums.length; j++) {
if (nums[i] + 1 == nums[j] || nums[i] == nums[j]) {
count += 1;
}
}
// 将最大的赋值给res
res = Math.max(count, res);
}
return res;
}
2、复杂度分析
时间复杂度：因为是双层循环遍历，所以时间复杂度是O(N^2)
空间复杂度：在双层遍历中，并没有产生额外的数组，只是定义了两个临时遍历，所以空间复杂度为O(1)
解法二：两次遍历 + HashMapHashMap + 两次遍历的思想也比较简单，第一次遍历是统计每个元素出现的次数，并且将元素的值作为key，出现的次数作为val 存入到 HashMap 中，第二次遍历是遍历 HashMap ，判断 HashMap 中是否存在比当前key+1的key，如果存在这统计出这两个key一共出现的次数，最后返回出现最多的次数。
1、解题代码
public static int findLHSByHashMap(int[] nums) {
// 记录最大的和谐子序列长度
int res = 0;
Map hashMap = new HashMap<>();
// 第一层遍历，当前元素默认为最小的元素
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
}
// 遍历整个map
for (int key : hashMap.keySet()) {
if (hashMap.containsKey(key + 1)) {
res = Math.max(res, hashMap.get(key) + hashMap.get(key + 1));
}
}
return res;
}
2、复杂度分析
时间复杂度：虽然遍历了两次，但是没有出现双层循环，所以时间复杂度是O(N)
空间复杂度：这里新增了 HashMap 的对象，所以空间复杂度为O(N)
解法三：单次遍历 + HashMap这种方法是前面一种方法的优化，将两次循环优化成一次循环，可以提升代码的执行效率，思想也比较简单，就是将元素 X 添加到 Map 集合后，同时判断出 X 与 X-1 组成的和谐数组长度和 X 与 X+1 组成的和谐数组长度，取两者中最大的一个。
1、解题代码
public static int findLHSByMap(int[] nums) {
// 记录最大的和谐子序列长度
int res = 0;
Map hashMap = new HashMap<>();
// 第一层遍历，当前元素默认为最小的元素
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
// 判断是否包含key+1的key
if (hashMap.containsKey(nums[i] + 1)) {
res = Math.max(res, hashMap.get(nums[i]) + hashMap.get(nums[i] + 1));
}
// 判断是否包含key-1的key
if (hashMap.containsKey(nums[i] - 1)) {
res = Math.max(res, hashMap.get(nums[i]) + hashMap.get(nums[i] - 1));
}
}
return res;
}
2、复杂度分析
时间复杂度：虽然遍历了两次，但是没有出现双层循环，所以时间复杂度是O(N)
空间复杂度：这里新增了 HashMap 的对象，所以空间复杂度为O(N)
平头哥的技术博文（id：pingtouge_java）
作者：平头哥，学会伺机而动，实现弯道超车
