class Solution {
public:
int findLHS(vector<int>& nums) {
map<int, int> freqs;
for (int n : nums) {
freqs[n]++;
}
int longest = 0;
int lastNum = 0;
int lastFreq = 0;
for (pair<int, int> p : freqs) {
int freq2 = 0;
if (lastFreq && p.first == lastNum + 1) {
freq2 = p.second + lastFreq;
}
longest = max(longest, freq2);
lastNum = p.first;
lastFreq = p.second;
}
return longest;
}
};
C++ Solution


@alexander Good solution! You idea is similar to sorting. unordered_map is required for O(n) time complexity.

@zestypanda Thanks. Yes I agree sorted map is not necessary given that you can probe the neighber.

Really great solution! using map default comparator (less).
I made a slight change to reduce some judgements.class Solution { public: int findLHS(vector<int>& nums) { map<int, int> freqs; for (int n : nums) { freqs[n]++; } int lastNum = freqs.begin()>first; int lastFreq = 0; int longest = 0; for (pair<int, int> p : freqs) { int freq2 = 0; if (p.first == lastNum + 1) { freq2 = p.second + lastFreq; } longest = max(longest, freq2); lastNum = p.first; lastFreq = p.second; } return longest; } };