内容

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.

---

思路

既然子序列中最大值和最小值差别为1，那么就是说，这两个元素处于排序后数组中的相邻位置，所以这里先对数组排序。
然后将这些元素出现的次数存储起来用对象表示。
最后依次统计相邻元素里出现次数最多的值，也就是最大子序列的长度。

---

代码

/**
最长和谐子序列

思路，既然子序列中最大值和最小值差别为1，那么就是说，这两个元素处于排序后数组中的相邻位置，所以这里先对数组排序。
然后将这些元素出现的次数存储起来用对象表示。
最后依次统计相邻元素里出现次数最多的值，也就是最大子序列的长度。
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
    var map = {};

    nums.sort(function (a, b) {
        return a - b;
    })

    nums.forEach(function (item) {
        if (map[item] == null) {
            map[item] = 1;
        } else {
            map[item] += 1;
        }
    })

    var keys = Object.keys(map);
    var maxLength = 0;
    for (var i = 0; i < keys.length; i++) {
        var nowKey = keys[i];
        var nextKey = keys[i + 1];
        var nowVal = map[nowKey];
        var nextVal = map[nextKey];

        if (Math.abs(nextKey - nowKey) == 1 && nowVal + nextVal > maxLength) {
            maxLength = nowVal + nextVal;
        }
    }

    return maxLength;
};

---

回到目录