2019-06-20.md

毎日一题 - 594. Longest Harmonious Subsequence

信息卡片

• 时间：2019-06-20
• 题目链接：https://leetcode.com/problems/longest-harmonious-subsequence/
• tag：Array

题目描述

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

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

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

思路

1. 将数组中的值作为一个对象中的属性，出现的次数就是属性值
2. 属性差一的值相加，获取最大的，否则返回0；

参考答案

/**
 * @param {number[]} nums
 * @return {number}
 * 使用ES6中的Map
 */
var findLHS = function(nums) {
    if(!nums.length) return 0;
    const map = new Map();
    let max = 0;
    for(let i = 0; i<nums.length; i++) {
      let target = nums[i]
      if (map.has(target)) {
        map.set(target, map.get(target)+1);
      } else {
        map.set(target, 1);
      }
    }
    for (let key of map.keys()) {
      if(map.has(key+1)) {
        max = Math.max(map.get(key)+map.get(key+1), max);
      }
    }
    return max
};

其它优秀解法

/**
 * @param {number[]} nums
 * @return {number}
 * for...in遍历
 */
var findLHS = function(nums) {
    if(!nums.length) return 0;
    const counts = {};
    let max = 0;
    for(let i = 0; i<nums.length; i++) {
      if (counts[nums[i]]) {
        counts[nums[i]] += 1;
      } else {
        counts[nums[i]] = 1;
      }
    }
    for (let key in counts) { // for...in性能低
      if(counts[+key+1]) {
        max = Math.max(counts[key]+counts[+key+1], max)
      }
    }
    return max
};

/**
 * @param {number[]} nums
 * @return {number}
 * 普通遍历
 */
var findLHS = function(nums) {
    if(!nums.length) return 0;
    const counts = {};
    let max = 0;
    for(let i = 0; i<nums.length; i++) {
      if (counts[nums[i]]) {
        counts[nums[i]] += 1;
      } else {
        counts[nums[i]] = 1;
      }
    }
    for (let i = 0; i < nums.length; i++) { // 有多余的无效遍历
      if (counts[nums[i] + 1]) {
        max = Math.max(max, counts[nums[i]] + counts[nums[i] + 1]);
      }
    }
    return max
};