这是我参与11月更文挑战的第20天,活动详情查看:2021最后一次更文挑战
题目
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1
。
现在,给你一个整数数组 nums
,请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
示例
输入: nums = [1,3,2,2,5,2,3,7]
输出: 5
解释: 最长的和谐子序列是 [3,2,2,2,3]
复制代码
输入: nums = [1,2,3,4]
输出: 2
复制代码
输入: nums = [1,1,1,1]
输出: 0
复制代码
提示
1 <= nums.length <= 2 * 10^4
-10^9 <= nums[i] <= 10^9
解题思路
双指针
题目要求是找到数组的子序列(通过删除一些元素或不删除元素,且不改变其余元素的顺序而得)
,很多人可能会想着那就没办法先排序了,然后就在想还有什么解题但方法。
但其实它这里面有个坑在这,和谐数组的定义是数组中的最大值和最小值直接的距离为1
,那么也就是说,数组中只有相邻的两个数才能构成一个和谐数组,其余元素没得参合进来,那么我们就可以直接进行排序操作了,不是相邻的两个元素都进行删除操作,仅保留所需元素,这样得出的长度与排序前的长度也是一致的,并不会导致结果发生变化。
class Solution {
public int findLHS(int[] nums) {
// 排序
Arrays.sort(nums);
int max = 0;
for(int left = 0, right = 1; right < nums.length; ++right){
// 判断如果左边元素与右边元素相差超过1,则指针右移
while(left < right && nums[right] - nums[left] > 1){
++left;
}
// 判断是否为和谐数组
if(nums[right] - nums[left] == 1){
// 更新结果
max = Math.max(max, right - left + 1);
}
}
return max;
}
}
复制代码
复杂度分析
- 时间复杂度:
- 空间复杂度:
最后
文章有写的不好的地方,请大佬们不吝赐教,错误是最能让人成长的,愿我与大佬间的距离逐渐缩短!
如果觉得文章对你有帮助,请 点赞、收藏、关注、评论 一键四连支持,你的支持就是我创作最大的动力!!!
近期评论