[leetcode] Longest Harmonious Subsequence

임택·2021년 2월 5일
0

problem

code

-sol1

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?

-sol2: better hashmap solution

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

-sol3: hashmap with one loop

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)

profile
캬-!

0개의 댓글