leetcode 594. 最长和谐子序列

leetcode 594. 最长和谐子序列

题目描述

题目描述 评论 (497) 题解 (693) 提交记录 594. 最长和谐子序列

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

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

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

输入：nums = [1,3,2,2,5,2,3,7] 输出：5 解释：最长的和谐子序列是 [3,2,2,2,3] 示例 2：

输入：nums = [1,2,3,4] 输出：2 示例 3：

输入：nums = [1,1,1,1] 输出：0

提示：

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

解题思路

子序列:在数组num中存在的数的数组,比如[12222344555]

那么[12345]可以是子序列[122345]也可以是子序列[1345]也可以是子序列

但是[112345]不是子序列,因为有两个1出现,而主数组num只有一个1

那么最长的和谐子序列可以是[12222],也可以是[44555] 长度都为5 ,

法1

排序+三指针\

我们可以采用排序的方法,然后找出数字相差1 的相邻数组的最长数组

1. 排序数组
2. 定义3个指针,(i)一个指向开始的位置,(k)一个指向开始位置下一个不同的数的位置,(j)一个寻找下两个不同数的位置,长度=i-k,
3. i,k移向下一位置,继续循环直到结束位置

但是还有一些细节问题需要判断,

1. 结尾位置的长度 计算
2. 如果只有一种或者两种元素怎么办.

这些情况需要单独处理,需要判断出来

1. 只有一种元素 (长度=0)
2. 两种元素长度=len(num)

• 时间复杂度(O(nlogn))
• 空间复杂度(O(n))

执行结果

法1

func findLHS(nums []int) (r int) {
 sort.Ints(nums)
 if nums[0] == nums[len(nums)-1] {
  return
 }
 k, i := 0, 0
 for k = 0; k < len(nums) && nums[k] == nums[0]; k++ {
 }
 for j := k + 1; j < len(nums); j++ {
  if nums[j] > nums[k] {
   if r < j-i && nums[i]+1 == nums[k] {
    r = j - i
   }
   i = k
   k = j
  }
 }
 if len(nums[i:]) > r && nums[i]+1 == nums[k] {
  r = len(nums[i:])
 }
 return
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 48 ms , 在所有 Go 提交中击败了 66.12% 的用户 内存消耗： 6.5 MB , 在所有 Go 提交中击败了 92.56% 的用户 通过测试用例： 206 / 206 炫耀一下:

法2

法3