class Solution {
public int findLHS(int[] nums) {
int len = nums.length;
if(len == 1) return 0;
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums)
{
if(map.containsKey(n))
{
map.put(n, map.get(n) + 1);
}
else
{
map.put(n, 1);
}
}
Set<Integer> keys = map.keySet();
Integer[] keyArr = keys.stream().toArray(Integer[]::new);
Arrays.sort(keyArr);
Integer prev = null;
Integer count = 0;
for (Integer key : keyArr)
{
if (prev == null)
{
prev = key;
}
int diff = key - prev;
// System.out.println("diff: " + diff + " key:" + key + " prev:" + prev);
if (key - prev == 1)
{
Integer temp = map.get(prev) + map.get(key);
// System.out.println("temp: " + temp + " count:" + count);
if (temp > count) count = temp;
}
prev = key;
}
return count;
}
}
Time: O(NlogN), M <= N
Space: O(N), hmmm HashMap?
public class Solution {
public int findLHS(int[] nums) {
HashMap < Integer, Integer > map = new HashMap < > ();
int res = 0;
for (int num: nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int key: map.keySet()) {
if (map.containsKey(key + 1))
res = Math.max(res, map.get(key) + map.get(key + 1));
}
return res;
}
}
public class Solution {
public int findLHS(int[] nums) {
HashMap < Integer, Integer > map = new HashMap < > ();
int res = 0;
for (int num: nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.containsKey(num + 1))
res = Math.max(res, map.get(num) + map.get(num + 1));
if (map.containsKey(num - 1))
res = Math.max(res, map.get(num) + map.get(num - 1));
}
return res;
}
}
Time: O(N)
Space: O(N)