[数据结构与算法]LeetCode 594. Longest Harmonious Subsequence

We define a harmonious array as an array where the difference between its maximum value and its minimum value is?exactly?1.

Given an integer array?nums, return?the length of its longest harmonious subsequence among all its possible subsequences.

A?subsequence?of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Example 2:

Input: nums = [1,2,3,4]
Output: 2

Example 3:

Input: nums = [1,1,1,1]
Output: 0

Constraints:

• 1 <= nums.length <= 2 * 104
• -109?<= nums[i] <= 109

这题是要求一个数组里，最大和最小元素之差为1的subsequence的最长长度。想得太复杂了因为想到了以前头大的longest subsequence系列问题。看了答案才知道其实很简单，其实就是求这个数组里相差为1的数字的个数的max。

1. Brute force

首先是brute force的做法，对数组里每个元素都进行一遍操作：遍历整个数组，如果遇到了和它一样的或者比他大1的，就算进去。这里刚开始想着我既可以小1也可以大1，但其实因为在内层for loop里是又扫了一遍整个数组（对，注意这里要再扫一次整个数组），所以其实小1的情况肯定也会被cover进来，就只用看大1就行。另外还需要一个boolean flag来记录是否存在比它大1的，否则可能全都是同一个元素，这种也不算。然鹅这个做法TLE了。O(n^2)

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

2. sorting

刚开始想岔了，因为想着sebsequence是和顺序有关的所以不能sort……嗯……这里因为不care数字大小的顺序所以sort是没问题的。sort完以后，我们就只需要按顺序计算相邻的两个数字一共有多少个。这里要写出clean code也需要一点小技巧，which我刚开始就没get到。这里一共有两种情况，一种情况是当前这个数字是前面数字的+1，这时候我们就计算有多少个这个数字，然后再和前面的个数相加，和result比大小。另一种情况是当前这个数字是一个全新的开始，这时候只需要计算有多少个这个数字就行。所以是if else里面还要套一层while loop来算个数。外层看数字+1的时候和前面的数字比，内层计算个数的时候和后面的数字比。O(nlogn)

Runtime:?16 ms, faster than?97.92%?of?Java?online submissions for?Longest Harmonious Subsequence.

Memory Usage:?54.6 MB, less than?70.64%?of?Java?online submissions for?Longest Harmonious Subsequence.

class Solution {
    public int findLHS(int[] nums) {
        int result = 0;
        Arrays.sort(nums);
        int prevCount = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 1;  // the current number
            // if it's the first one for the +1 number
            if (i > 0 && nums[i] - nums[i - 1] == 1) {
                while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
                    i++;
                    count++;
                }
                result = Math.max(result, count + prevCount);
            } else {
                // if it's a fresh start
                while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
                    count++;
                    i++;
                }
            }
            prevCount = count;
        }
        return result;
    }
}

3. HashMap

就，其实更简单了……就是计算这个数组里相邻的数字的个数之和max，那就用个hashmap记录每个数字出现的次数就行了。然后遍历一遍这个map的keyset，看看key + 1是否也在map里，如果在的话加加看有多少就行。O(n)。

Runtime:?44 ms, faster than?46.59%?of?Java?online submissions for?Longest Harmonious Subsequence.

Memory Usage:?67.1 MB, less than?40.93%?of?Java?online submissions for?Longest Harmonious Subsequence.

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

4. 改进版hashmap

就是把上面那个的两个for loop简化成一个for loop，一遍put map的时候一边更新result。put完以后看看map里有没有比它大1或者小1的数字，如果有就加上它的count。这里需要判断both +1和-1因为是按照原数组的排列顺序来的。也是O(n)

Runtime:?59 ms, faster than?20.81%?of?Java?online submissions for?Longest Harmonious Subsequence.

Memory Usage:?68 MB, less than?25.78%?of?Java?online submissions for?Longest Harmonious Subsequence.

class Solution {
    public int findLHS(int[] nums) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int 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;
    }
}