594.最长和谐子序列

链接：594.最长和谐子序列
难度：Easy
标签：数组、哈希表、计数、排序、滑动窗口
简介：现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

题解 1 - typescript

• 编辑时间：2021-11-20
• 执行用时：120ms
• 内存消耗：48.6MB
• 编程语言：typescript
• 解法介绍：哈希存储。

function findLHS(nums: number[]): number {
  const map = new Map<number, number>();
  for (const num of nums) map.set(num, (map.get(num) ?? 0) + 1);
  const list = Array.from(map.entries()).sort(([num1], [num2]) => num1 - num2);
  let ans = 0;
  for (let i = 0, l = list.length; i < l - 1; i++) {
    const [num1, cnt1] = list[i];
    const [num2, cnt2] = list[i + 1];
    if (num2 !== num1 + 1) continue;
    ans = Math.max(ans, cnt1 + cnt2);
  }
  return ans;
}

题解 2 - c

• 编辑时间：2021-11-20
• 执行用时：52ms
• 内存消耗：8.6MB
• 编程语言：c
• 解法介绍：排序。

int comp(int *num1, int *num2){
    return *num1 - *num2;
}
int findLHS(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), comp);
    int ans = 0, left = 0, right = 0;
    while(right < numsSize - 1){
        while(right < numsSize - 1 && nums[right] == nums[left]) right++;
        while(right < numsSize - 1 && nums[right] == nums[right + 1]) right++;
        if(nums[left] == nums[right] - 1 && right - left + 1 > ans) ans = right - left + 1;
        while(nums[left] != nums[right]) left++;
    }
    return ans;
}