LeetCode算法题-Longest Harmonious Subsequence（Java实现）

佚名 5年前 (2019-03-08) 算法 1162人围观抢沙发百度已收录

这是悦乐书的第270次更新，第284篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第136题（顺位题号是594）。我们定义一个和谐数组是一个数组，其最大值和最小值之间的差值恰好为1。给定一个整数数组，在其所有可能的子序列中找到其最长的和谐子序列的长度。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：[1,3,2,2,5,2,3,7]
输出：5
说明：最长的和谐子序列是[3,2,2,2,3]。

注意：输入数组的长度不会超过20,000。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

直接使用两层for循环，依次遍历元素，如果当前元素在数组中不存在与之值相差为1的数，标志flag就为false，那么此元素就不参与计算，反之存在，就把自己出现的次数与其值相差为1的元素的出现次数加起来，并且flag改为true，取最大值即可。

public int findLHS(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    int result = 0;
    for(int i=0; i<nums.length; i++){
        boolean flag = false;
        int count = 0;
        for (int j=0; j<nums.length; j++) {
            if (nums[i] == nums[j]) {
                count++;
            } else if (nums[i] == nums[j]-1) {
                flag = true;
                count++;
            }
        }
        if (flag) {
            result = Math.max(result, count);
        }
    }
    return result;
}

03 第二种解法

先对数组进行升序排序，借助Arrays.sort方法来实现，然后遍历数组的元素。

排完序后，可以先将两种特殊情况直接返回结果，如果排序后的数组第一个元素与最后一个元素值相等，直接返回0；如果数组第一个元素与最后一个元素值相差1，返回数组长度。

如果当前元素连续出现，我们需要先将其出现次数记录下来，使用变量preCount来存值，在遇到与其值相差为1的元素时，再将与其值相差为1的元素的出现次数记录下来，加上preCount的值，就表示此和谐数组的长度，再去与所有可能的和谐数组长度做比较取最大值。

如果当前元素不是连续出现，那么preCount的值就为1，表示当前元素只出现了一次，然后判断下一个元素是否与其值相差1，如果下一个元素符合条件，就找到该元素出现的次数，加上preCount的值，两次数之和与最大值取较大者。

public int findLHS2(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    Arrays.sort(nums);
    if (nums[0] == nums[nums.length-1]) {
        return 0;
    }
    if (nums[0] == nums[nums.length-1]-1) {
        return nums.length;
    }
    int preCount = 1, result = 0;
    for (int i = 0; i < nums.length; i++) {
        int count = 1;
        if (i > 0 && nums[i] - nums[i - 1] == 1) {
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                count++;
                i++;
            }
            result = Math.max(result, count + preCount);
            preCount = count;
        } else {
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                count++;
                i++;
            }
            preCount = count;
        }
    }
    return result;
}

04 第三种解法

使用HashMap，以数组中的每个元素为key，其出现次数为value，然后遍历map中的每个key，如果map中含有比当前key值大1的key，那么将当前key所对应的value与当前key加1后所对应的value相加，就表示一组和谐数组，在所有可能的和谐数组中找出最大值即可。为了避免溢出，HashMap中的key的类型取Long。

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

05 第四种解法

我们可以将上面的解法再精简下，变成一个循环。有一点需要注意，与当前元素能够组成和谐数组的数，可能比自己大1，也可能比自己小1，并且可能还在当前元素的后面出现，所以需要将两种情况都考虑进去。

public int findLHS4(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    HashMap<Long, Integer> map = new HashMap<Long, Integer>();
    int result = 0;
    for (long n: nums) {
        map.put(n, map.getOrDefault(n, 0)+1);
        if (map.containsKey(n+1)) {
            result = Math.max(result, map.get(n) + map.get(n+1));
        }
        if (map.containsKey(n-1)) {
            result = Math.max(result, map.get(n) + map.get(n-1));
        }
    }
    return result;
}