Problem
https://leetcode.com/problems/longest-harmonious-subsequence/description/
题目大意：找一个最长子序列，要求子序列中最大值和最小值的差是1。
We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
Example 1:
Input: [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Note: The length of the input array will not exceed 20,000.
Solution1: HashTable
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 127 ms class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int, int> counts; int ans = 0; for (int num : nums) { ++counts[num]; int l = counts[num - 1]; int h = counts[num + 1]; if (l || h) ans = max(ans, counts[num] + max(l, h)); } return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Running time: 109 ms class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int, int> counts; int ans = 0; for (int num : nums) { const int c = ++counts[num]; auto it1 = counts.find(num - 1); auto it2 = counts.find(num + 1); if (it1 != counts.end()) ans = max(ans, c + it1->second); if (it2 != counts.end()) ans = max(ans, c + it2->second); } return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 102 ms class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int, int> counts; int ans = 0; for (int num : nums) ++counts[num]; for (const auto& p : counts) { auto it1 = counts.find(p.first - 1); auto it2 = counts.find(p.first + 1); if (it1 != counts.end()) ans = max(ans, p.second + it1->second); if (it2 != counts.end()) ans = max(ans, p.second + it2->second); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment