Leetcode594.最长和谐子序列

题目

594. 最长和谐子序列

算法标签: 滑动窗口, 哈希表

思路

先将数组进行排序, 检查两个相邻的但是不相等的数字的差值是否是$1$, 如果是$1$更新答案

滑动窗口代码

#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>

using namespace std;

class Solution {
   
public:
    int findLHS(vector<int>& nums) {
   
        sort(nums.begin(), nums.end());
        int l = 0, r = 0, n = nums.size();
        int ans = 0;

        while (r < n) {
   
            while (l <= r && nums[r] - nums[l] > 1) l++;
            if (nums[r] - nums[l] == 1) ans = max(ans, r - l + 1);
            r++;
        }
        
        return ans;
    }
};

哈希表代码

#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>

using namespace std;

class Solution {
   
public:
    int findLHS(vector<int>& nums) {
   
        map<int, int> mp;
        int n = nums.size();
        
        for (int val : nums) mp[val]++;
        
        int ans = 0;
        for (auto [val, cnt] : mp) {
   
            if (mp.count(val + 1)) {
   
                ans = max(ans, cnt + mp[val + 1]);
            }
        }
        
        return ans;
    }
};