排序算法之最长和谐子序列

题目

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

示例3：

输入：nums = [1,1,1,1]
输出：0      

解题思路

1. 将数组按照从小到大进行排序，我们只需要依次找到相邻两个连续相同元素的子序列，检查该这两个子序列的元素的之差是否为 1.
2. 利用滑动窗口的做法，begin 指向第一个连续相同元素的子序列的第一个元素，end 指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者的元素之差为 1，则当前的和谐子序列的长度即为两个子序列的长度之和，等于 end−begin+1。

代码实现

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int begin = 0;
        int res = 0;
        for (int end = 0; end < nums.length; end++) {
            while (nums[end] - nums[begin] > 1) {
                begin++;
            }
            if (nums[end] - nums[begin] == 1) {
                res = Math.max(res, end - begin + 1);
            }
        }
        return res;
    }
}      

最后

复杂度分析

• 时间复杂度：O(NlogN)。
• 空间复杂度：O(1)，需要常数个空间保存中间变量。

• ​​# UE4：来为我们的角色制作一个血条吧​​
• ​​使用 Google Breakpad 来助力解决程序崩溃​​
• ​​UE4 多人游戏服务器探索​​
• ​​使用虚幻引擎自动化工具实现自动化部署​​
• ​​如何在 UE4 中制作一扇自动开启的大门​​
• ​​如何在 UE4 中用代码去控制角色移动​​
• ​​如何给 UE4 场景添加游戏角色​​
• ​​UE4：Android 平台开发实践指南​​
• ​​UE4 开发避坑指南（持续更新）​​
• ​​新年开工啦，放个小烟花庆祝一下​​
• ​​聊聊与苹果审核员的爱恨情仇(下)​​
• ​​聊聊与苹果审核员的爱恨情仇(上)​​
• ​​一名普通工具人的 2021 | 2021年终总结​​
• ​​二叉树刷题总结：二叉搜索树的属性​​
• ​​二叉树总结：二叉树的属性​​
• ​​二叉树总结：二叉树的修改与构造​​
• ​​StoreKit2 有这么香？嗯，我试过了，真香​​
• ​​看完这篇文章，再也不怕面试官问我如何构造二叉树啦！​​
• ​​那帮做游戏的又想让大家氪金，太坏了！​​
• ​​手把手带你撸一个网易云音乐首页 | 适配篇​​
• ​​手把手带你撸一个网易云音乐首页（三）​​
• ​​手把手带你撸一个网易云音乐首页（二）​​
• ​​手把手带你撸一个网易云音乐首页（一）​​
• ​​代码要写注释吗？写你就输了​​
• ​​Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿​​
• ​​iOS 优雅的处理网络数据，你真的会吗？不如看看这篇​​
• ​​UICollectionView 自定义布局！看这篇就够了​​

1. 关注公众号--- HelloWorld杰少