Simple Java HashMap Solution


  • 19
    • The idea is to keep a count of all the numbers, and eventually for each of the numbers, check if there's any adjacent number. If it's present, then add the count of both - since these two numbers form subsequence in the array.

    Update : from @harkness comment, we don't need to check both +1 and -1;

    public int findLHS(int[] nums) {
        Map<Long, Integer> map = new HashMap<>();
        for (long num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int result = 0;
        for (long key : map.keySet()) {
            if (map.containsKey(key + 1)) {
                result = Math.max(result, map.get(key + 1) + map.get(key));
            }
        }
        return result;
    }

  • 6
    H

    You don't need to check both key+1 and key-1. Checking one of them is enough.


  • 1
    Y

    Any reason to use long instead of int?


  • 4

    @yl
    to handle this :

    findLHS(new int[]{-2147483648 , 2147483647});
    //2147483647 + 1 = -2147483648 , and we don't want that.

  • 1
    Y

    @jaqenhgar Yes you are right, they should add this to test case.


  • 0

    @yl Oh I wasn't aware that it's not there!
    @1337c0d3r We're missing a test case. My answer is 0, and OJ is 2.


  • 1
    Y

    @jaqenhgar Great catch :)


  • 0
    K

    @harkness So clever u are.


  • 0
    J

    Great solution! Here is the C++ version

    class Solution {
    public:
        int findLHS(vector<int>& nums) {
            unordered_map<int, int> map;
            for(auto num : nums) {
                if(map.find(num) == map.end())
                    map[num] = 1;
                else
                    map[num] += 1;
            }
            int result = 0;
            for (auto iter = map.begin(); iter != map.end(); ++iter)
                if (map.find(iter->first + 1) != map.end())
                    result = max(result, iter->second + map[iter->first + 1]);
            return result;
        }
    };
    

  • 1
    Z

    @jtimberlakers you don't have to check whether num is in the map when counting the frequency. If num doesn't exist, default constructor will generate one. So "map[num]++;" will be sufficient.


  • 0

    @jaqenhgar If we use TreeMap will it optimize the solution, because we are searching for nearby keys always (key+1) ?


  • 0
    A

    @harkness Can you specify the reason not to check key-1? Thanks


  • 1
    H

    @arthursunbao if key and key-1 form a valid answer, then we should be able to find it when checking key-1 as the key.


  • 0
    G

    @jaqenhgar yes,we are just same,but I sort the nums firstly,then use HashMap to count it.

    public class Solution {
        public int findLHS(int[] nums) {
           Arrays.sort(nums);
            Map<Integer,Integer> map=new HashMap<>();
           int max=0;
           for(Integer i:nums){
               map.put(i,map.getOrDefault(i,0)+1);
           }
           for(int i=1;i<nums.length;i++){
               if(nums[i]-nums[i-1]==1)max=Math.max(max,map.get(nums[i])+map.get(nums[i-1]));
           }
           return max;
        }
    }
    

  • 0
    A

    In this solution, it has duplicate calculation, how to improve it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.