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;}
};