Problem
Solution
Analysis
Python implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
class (object): def findLHS(self, nums): """ :type nums: List[int] :rtype: int """ counter = dict() res = 0 for num in nums: counter[num] = counter.get(num, 0)+1 for key, val in counter.items(): if key+1 in counter: res = max(res, counter[key+1]+val) return res
|
Java implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
class { public int findLHS(int[] nums) { Map<Integer, Integer> counter = new HashMap<>(); int res = 0; for(int num : nums){ counter.put(num, counter.getOrDefault(num, 0)+1); } for(int num : counter.keySet()){ if(counter.containsKey(num+1)){ int curRes = counter.get(num)+counter.get(num+1); res = curRes > res ? curRes : res; } } return res; } }
|
Time complexity
O(n).
Space complexity
O(n).
Link
594. Longest Harmonious Subsequence
(中文版) 算法笔记: 力扣#594 最长和谐子序列
近期评论