j
jaryue
V1
2023/04/27阅读:13主题:默认主题
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 的相邻数组的最长数组
-
排序数组 -
定义3个指针,(i)一个指向开始的位置,(k)一个指向开始位置下一个不同的数的位置,(j)一个寻找下两个不同数的位置,长度=i-k, -
i,k移向下一位置,继续循环直到结束位置
但是还有一些细节问题需要判断,
-
结尾位置的长度 计算 -
如果只有一种或者两种元素怎么办.
这些情况需要单独处理,需要判断出来
-
只有一种元素 (长度=0) -
两种元素长度=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
作者介绍
j
jaryue
V1