排序算法之最長和諧子序列

題目

和諧數組是指一個數組裡元素的最大值和最小值之間的差别 正好是 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傑少