力扣刷题笔记【双指针】 → 594 最长和谐子序列

发表于

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战

题目

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

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

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

示例

1
2
3
ini复制代码输入： nums = [1,3,2,2,5,2,3,7]
输出： 5
解释： 最长的和谐子序列是 [3,2,2,2,3]
1
2
ini复制代码输入： nums = [1,2,3,4]
输出： 2
1
2
ini复制代码输入： nums = [1,1,1,1]
输出： 0

提示

  • 1 <= nums.length <= 2 * 10^4
  • -10^9 <= nums[i] <= 10^9

解题思路

双指针

题目要求是找到数组的子序列(通过删除一些元素或不删除元素，且不改变其余元素的顺序而得),很多人可能会想着那就没办法先排序了，然后就在想还有什么解题但方法。

但其实它这里面有个坑在这，和谐数组的定义是数组中的最大值和最小值直接的距离为1,那么也就是说，数组中只有相邻的两个数才能构成一个和谐数组，其余元素没得参合进来，那么我们就可以直接进行排序操作了，不是相邻的两个元素都进行删除操作，仅保留所需元素，这样得出的长度与排序前的长度也是一致的，并不会导致结果发生变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java复制代码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;
    }
}

复杂度分析

  • 时间复杂度：O(NlogN)O(NlogN)O(NlogN)
  • 空间复杂度：O(1)O(1)O(1)

最后

文章有写的不好的地方，请大佬们不吝赐教，错误是最能让人成长的，愿我与大佬间的距离逐渐缩短！

如果觉得文章对你有帮助，请 点赞、收藏、关注、评论 一键四连支持，你的支持就是我创作最大的动力！！！

题目出处: leetcode-cn.com/problems/lo…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%