LeetCode 594. Longest Harmonious Subsequence

题目

• 对和谐数组的定义是，数组内的最大元素 - 最小元素的值为 1
• 给定一给数组，返回用其子序列可形成的和谐数组的最大长度

思路

• 对数组的元素频率进行统计 freq
• 遍历数组的元素 num，判断是否 num + 1 存在，这过程中的 freq[num] + freq[num+1] 就是和谐数组的长度
• 记录过程中的最大值

代码

class Solution {
public:int solution1(vector<int>& nums) {set<int> st;map<int, int> ht;for (auto num : nums) {ht[num]++;st.insert(num);}int ans = 0;for (auto n : st) {if (st.count(n+1)) {ans = max(ans, ht[n] + ht[n+1]);}}return ans;}int solution2(vector<int>& nums) {sort(nums.begin(), nums.end());map<int, int> mp;for (auto num : nums) {mp[num]++;}int ans = 0;for (int i = 0; i < nums.size(); i+= mp[nums[i]]) {int num = nums[i];int len = mp[num];if (i + len < nums.size() && nums[i + mp[num]] == num + 1) {ans = max(ans, mp[num] + mp[num + 1]);}}return ans;}int findLHS(vector<int>& nums) {//return solution1(nums);return solution2(nums);}
};