This is the 20th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

The title

A harmonious array is an array in which the difference between the maximum and minimum values is exactly 1.

Now, given an integer array nums, find the length of the longest harmonious subsequence of all possible subsequences.

A subsequence of an array is a sequence derived from an array that can be obtained by deleting some elements or not deleting elements and not changing the order of the rest of the elements.

The sample

Input: nums = [1,3,2,2,5,2,3,7] output: 5 explanation: the longest concord sequence is [3,2,2, 3]Copy the code
Input: nums = [1,2,3,4Copy the code
Input: nums = [1,1,1,1] output: 0Copy the code

prompt

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

Their thinking

Double pointer

Finding the subsequence of the array (by deleting some elements or not deleting elements and not changing the order of the rest), many of you might think there’s no way to sort first, and then wonder what else you can do.

But in fact it that there is a hole in it, the definition of harmonious array is an array of the maximum and the minimum distance of 1 directly, so that is to say, only the adjacent two Numbers in the array to constitute a harmonious array, the rest of the elements have no ginseng to come in, so we can direct sorting operation, not the adjacent two elements are deleted, Keep only the required elements, so that the length is the same as before the sorting, and it does not change the result.

class Solution {
    public int findLHS(int[] nums) {
        / / sorting
        Arrays.sort(nums);
        int max = 0;
        for(int left = 0, right = 1; right < nums.length; ++right){
            If the difference between the left element and the right element is more than 1, the pointer moves right
            while(left < right && nums[right] - nums[left] > 1){
                ++left;
            }
            // Check whether it is a harmonious array
            if(nums[right] - nums[left] == 1) {// Update the result
                max = Math.max(max, right - left + 1); }}returnmax; }}Copy the code

Complexity analysis

  • O(NlogN)O(NlogN)O(NlogN)
  • Space complexity: O(1)O(1)O(1)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/lo…