leetcode 594. Longest Harmonious Subsequence | 594. 最长和谐子序列

向右看齐 2022-10-16 15:23 128阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/longest-harmonious-subsequence/][https_leetcode-cn.com_problems_longest-harmonious-subsequence]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 我的解法 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
测试用例

> \[1\]  
> \[1,2\]  
> \[2,1\]  
> \[3,1\]  
> \[3,1,1\]  
> \[3,5,5\]  
> \[1,3,5,7\]  
> \[2,2\]  
> \[1,2,1,2,1,2,1,2,1,2\]  
> \[3,3,3,2,2,2,1,1,1\]  
> \[3,3,2\]  
> \[1,3,2,2,5,2,3,7\]

import java.util.Arrays;
    
    class Solution { 
        public int findLHS(int[] nums) { 
            if (nums.length == 1) return 0;
            Arrays.sort(nums);
            int maxSum = 0;
            int numPre = Integer.MAX_VALUE;
            int cntPre = 0;
            int cntCur = 1;
            for (int i = 0; i < nums.length - 1; i++) { 
                if (nums[i] == nums[i + 1]) { 
                    cntCur++;
                } else { 
                    if (numPre + 1 == nums[i]) {  // update maxSum only when it's continuous
                        maxSum = Math.max(maxSum, cntPre + cntCur);
                    }
                    cntPre = cntCur;
                    cntCur = 1;
                    numPre = nums[i];
                }
            }
            // boundary: the last number
            if (nums[nums.length - 2] != nums[nums.length - 1]) { 
                cntPre = cntCur;
                cntCur = 1;
            }
            if (numPre + 1 == nums[nums.length - 1]) {  // update maxSum only when it's continuous
                maxSum = Math.max(maxSum, cntPre + cntCur);
            }
            return maxSum;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

#### 评论区优雅解法 ####

排序后，用两个指针，类似于窗口

class Solution { 
        public int findLHS(int[] nums) { 
            Arrays.sort(nums);
            int begin = 0,res = 0;
            for(int end = 0;end < nums.length;end++){ 
                while(nums[end] - nums[begin] > 1)
                     begin++;
                if(nums[end] - nums[begin] == 1)
                  res = Math.max(res,end - begin + 1);
            }
            return res;
        }
    }

[https_leetcode-cn.com_problems_longest-harmonious-subsequence]: https://leetcode-cn.com/problems/longest-harmonious-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221014/7a41d95e24004196b1311cc037f90093.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221014/fdcca85e0f224cb9be37a52948a55f4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221014/108cdb52bea348229837fde14baa55b3.png