“This is the 20th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

This is 594 on LeetCode. Longest concord subsequence, easy difficulty.

Tag: “Simulation”, “double pointer”, “sliding window”, “hash table”

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

Now, given an integer array numsnumsnums, ask you to 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.

Example 1:

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

Example 2:

Input: nums = [1,2,3,4Copy the code

Example 3:

Input: nums = [1,1,1,1] output: 0Copy the code

Tip:


  • 1 < = n u m s . l e n g t h < = 2 ∗ 1 0 4 1 <= nums.length <= 2 * 10^4

  • – 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9

Sort + slide window

An intuitive idea is to sort numsnumsnums first, then use the “double pointer” to realize the “sliding window” scan from front to back, count all the window lengths that meet the conditions, and take the maximum of all the length is the answer.

Code:

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        for (int i = 0, j = 0; j < n; j++) {
            while (j < n && nums[j] - nums[i] < 1) j++;
            while (j < n && i < j && nums[j] - nums[i] > 1) i++;
            if (i < n && j < n && nums[j] - nums[i] == 1) ans = Math.max(ans, j - i + 1);
        }
        returnans; }}Copy the code
  • Time complexity: The complexity of sorting is O(nlog⁡n)O(n\log{n})O(nlogn), and the complexity of sliding Windows through double Pointers is O(n)O(n)O(n) O(n). The overall complexity is O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(log⁡n)O(\log{n})O(logn)

Hash count

Subject of “harmonious subsequence” for 111, the most value of the difference and subsequence sorted must conform to the [a, a,.. and a + 1, a + 1], [a, a,.. and a + 1, a + 1], [a, a,.. and a + 1, a + 1] form, That is, the length of the eligible concord subsequence is the sum of the occurrence times of two adjacent numbers (the difference is 111).

We can use a “hash table” to record the occurrences of all nums[I]nums[I], and then find all possible number pairs (the difference between the two numbers is 111) by the complexity of O(n)O(n)O(n) O(n), and take the maximum of the length of “harmonious subsequence” that can be formed by all the number pairs that meet the conditions.

Code:

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        int ans = 0;
        for (int i : nums) {
            if (map.containsKey(i - 1)) {
                ans = Math.max(ans, map.get(i) + map.get(i - 1)); }}returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No. 594th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode by the start date, some of which have lock questions, we will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.