We define a harmonious array as an array where the difference between its maximum value and its minimum value isexactly1.Given an integer arraynums, returnthe length of its longest harmonious subsequence among all its possible subsequences.Asubsequenceof array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.Example 1:Input:nums [1,3,2,2,5,2,3,7]Output:5Explanation:The longest harmonious subsequence is [3,2,2,2,3].Example 2:Input:nums [1,2,3,4]Output:2Example 3:Input:nums [1,1,1,1]Output:0Constraints:1 nums.length 2 * 104-109 nums[i] 109这题是要求一个数组里最大和最小元素之差为1的subsequence的最长长度。想得太复杂了因为想到了以前头大的longest subsequence系列问题。看了答案才知道其实很简单其实就是求这个数组里相差为1的数字的个数的max。1. Brute force首先是brute force的做法对数组里每个元素都进行一遍操作遍历整个数组如果遇到了和它一样的或者比他大1的就算进去。这里刚开始想着我既可以小1也可以大1但其实因为在内层for loop里是又扫了一遍整个数组对注意这里要再扫一次整个数组所以其实小1的情况肯定也会被cover进来就只用看大1就行。另外还需要一个boolean flag来记录是否存在比它大1的否则可能全都是同一个元素这种也不算。然鹅这个做法TLE了。O(n^2)class Solution { public int findLHS(int[] nums) { int result 0; for (int i 0; i nums.length; i) { int count 0; boolean found false; for (int j 0; j nums.length; j) { if (nums[j] nums[i] 1) { found true; count; } else if (nums[j] nums[i]) { count; } } if (found) { result Math.max(result, count); } } return result; } }2. sorting刚开始想岔了因为想着sebsequence是和顺序有关的所以不能sort……嗯……这里因为不care数字大小的顺序所以sort是没问题的。2026.8.29下面这段别看了sort完以后我们就只需要按顺序计算相邻的两个数字一共有多少个。这里要写出clean code也需要一点小技巧which我刚开始就没get到。这里一共有两种情况一种情况是当前这个数字是前面数字的1这时候我们就计算有多少个这个数字然后再和前面的个数相加和result比大小。另一种情况是当前这个数字是一个全新的开始这时候只需要计算有多少个这个数字就行。所以是if else里面还要套一层while loop来算个数。外层看数字1的时候和前面的数字比内层计算个数的时候和后面的数字比。O(nlogn)Runtime: 16 ms, faster than 97.92% of Java online submissions for Longest Harmonious Subsequence.Memory Usage: 54.6 MB, less than 70.64% of Java online submissions for Longest Harmonious Subsequence.class Solution { public int findLHS(int[] nums) { int result 0; Arrays.sort(nums); int prevCount 0; for (int i 0; i nums.length; i) { int count 1; // the current number // if its the first one for the 1 number if (i 0 nums[i] - nums[i - 1] 1) { while (i 1 nums.length nums[i 1] nums[i]) { i; count; } result Math.max(result, count prevCount); } else { // if its a fresh start while (i 1 nums.length nums[i 1] nums[i]) { count; i; } } prevCount count; } return result; } }2026.8.29 看这个sliding window吧这题总是把自己绕进一个圈就是要计算count其实并不需要。用sliding window的思想sort完让window成为左右两边之差等于1的窗口。对于每一个right如果left比nums[right] - 1还小那就要while循环收缩left。如果nums[left] nums[right] - 1那就说明当前window是有效的可以和存的result比较。这里我总想着要count并不需要存count只要用index计算有多少就行了。有的时候会把自己绕进去如果left和right数字相等咋办比如第一波。这时候因为他俩不差1所以直接下一个循环接着挪right了left还是不动最后终于到right比left多1或者多更多的时候才会计算result或者移动left。class Solution { public int findLHS(int[] nums) { Arrays.sort(nums); int left 0; int result 0; for (int right 0; right nums.length; right) { while (nums[left] nums[right] - 1) { left; } if (nums[right] - nums[left] 1) { result Math.max(result, right - left 1); } } return result; } }3. HashMap就其实更简单了……就是计算这个数组里相邻的数字的个数之和max那就用个hashmap记录每个数字出现的次数就行了。然后遍历一遍这个map的keyset看看key 1是否也在map里如果在的话加加看有多少就行。O(n)。Runtime: 44 ms, faster than 46.59% of Java online submissions for Longest Harmonious Subsequence.Memory Usage: 67.1 MB, less than 40.93% of Java online submissions for Longest Harmonious Subsequence.class Solution { public int findLHS(int[] nums) { int result 0; MapInteger, Integer map new HashMap(); for (int n : nums) { map.put(n, map.getOrDefault(n, 0) 1); } for (int key : map.keySet()) { if (map.containsKey(key 1)) { result Math.max(result, map.get(key) map.get(key 1)); } } return result; } }4. 改进版hashmap就是把上面那个的两个for loop简化成一个for loop一遍put map的时候一边更新result。put完以后看看map里有没有比它大1或者小1的数字如果有就加上它的count。这里需要判断both 1和-1因为是按照原数组的排列顺序来的。也是O(n)Runtime: 59 ms, faster than 20.81% of Java online submissions for Longest Harmonious Subsequence.Memory Usage: 68 MB, less than 25.78% of Java online submissions for Longest Harmonious Subsequence.class Solution { public int findLHS(int[] nums) { int result 0; MapInteger, Integer map new HashMap(); for (int n : nums) { map.put(n, map.getOrDefault(n, 0) 1); if (map.containsKey(n 1)) { result Math.max(result, map.get(n) map.get(n 1)); } if (map.containsKey(n - 1)) { result Math.max(result, map.get(n) map.get(n - 1)); } } return result; } }
We define a harmonious array as an array where the difference between its maximum value and its minimum value isexactly1.Given an integer arraynums, returnthe length of its longest harmonious subsequence among all its possible subsequences.Asubsequenceof array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.Example 1:Input:nums [1,3,2,2,5,2,3,7]Output:5Explanation:The longest harmonious subsequence is [3,2,2,2,3].Example 2:Input:nums [1,2,3,4]Output:2Example 3:Input:nums [1,1,1,1]Output:0Constraints:1 nums.length 2 * 104-109 nums[i] 109这题是要求一个数组里最大和最小元素之差为1的subsequence的最长长度。想得太复杂了因为想到了以前头大的longest subsequence系列问题。看了答案才知道其实很简单其实就是求这个数组里相差为1的数字的个数的max。1. Brute force首先是brute force的做法对数组里每个元素都进行一遍操作遍历整个数组如果遇到了和它一样的或者比他大1的就算进去。这里刚开始想着我既可以小1也可以大1但其实因为在内层for loop里是又扫了一遍整个数组对注意这里要再扫一次整个数组所以其实小1的情况肯定也会被cover进来就只用看大1就行。另外还需要一个boolean flag来记录是否存在比它大1的否则可能全都是同一个元素这种也不算。然鹅这个做法TLE了。O(n^2)class Solution { public int findLHS(int[] nums) { int result 0; for (int i 0; i nums.length; i) { int count 0; boolean found false; for (int j 0; j nums.length; j) { if (nums[j] nums[i] 1) { found true; count; } else if (nums[j] nums[i]) { count; } } if (found) { result Math.max(result, count); } } return result; } }2. sorting刚开始想岔了因为想着sebsequence是和顺序有关的所以不能sort……嗯……这里因为不care数字大小的顺序所以sort是没问题的。2026.8.29下面这段别看了sort完以后我们就只需要按顺序计算相邻的两个数字一共有多少个。这里要写出clean code也需要一点小技巧which我刚开始就没get到。这里一共有两种情况一种情况是当前这个数字是前面数字的1这时候我们就计算有多少个这个数字然后再和前面的个数相加和result比大小。另一种情况是当前这个数字是一个全新的开始这时候只需要计算有多少个这个数字就行。所以是if else里面还要套一层while loop来算个数。外层看数字1的时候和前面的数字比内层计算个数的时候和后面的数字比。O(nlogn)Runtime: 16 ms, faster than 97.92% of Java online submissions for Longest Harmonious Subsequence.Memory Usage: 54.6 MB, less than 70.64% of Java online submissions for Longest Harmonious Subsequence.class Solution { public int findLHS(int[] nums) { int result 0; Arrays.sort(nums); int prevCount 0; for (int i 0; i nums.length; i) { int count 1; // the current number // if its the first one for the 1 number if (i 0 nums[i] - nums[i - 1] 1) { while (i 1 nums.length nums[i 1] nums[i]) { i; count; } result Math.max(result, count prevCount); } else { // if its a fresh start while (i 1 nums.length nums[i 1] nums[i]) { count; i; } } prevCount count; } return result; } }2026.8.29 看这个sliding window吧这题总是把自己绕进一个圈就是要计算count其实并不需要。用sliding window的思想sort完让window成为左右两边之差等于1的窗口。对于每一个right如果left比nums[right] - 1还小那就要while循环收缩left。如果nums[left] nums[right] - 1那就说明当前window是有效的可以和存的result比较。这里我总想着要count并不需要存count只要用index计算有多少就行了。有的时候会把自己绕进去如果left和right数字相等咋办比如第一波。这时候因为他俩不差1所以直接下一个循环接着挪right了left还是不动最后终于到right比left多1或者多更多的时候才会计算result或者移动left。class Solution { public int findLHS(int[] nums) { Arrays.sort(nums); int left 0; int result 0; for (int right 0; right nums.length; right) { while (nums[left] nums[right] - 1) { left; } if (nums[right] - nums[left] 1) { result Math.max(result, right - left 1); } } return result; } }3. HashMap就其实更简单了……就是计算这个数组里相邻的数字的个数之和max那就用个hashmap记录每个数字出现的次数就行了。然后遍历一遍这个map的keyset看看key 1是否也在map里如果在的话加加看有多少就行。O(n)。Runtime: 44 ms, faster than 46.59% of Java online submissions for Longest Harmonious Subsequence.Memory Usage: 67.1 MB, less than 40.93% of Java online submissions for Longest Harmonious Subsequence.class Solution { public int findLHS(int[] nums) { int result 0; MapInteger, Integer map new HashMap(); for (int n : nums) { map.put(n, map.getOrDefault(n, 0) 1); } for (int key : map.keySet()) { if (map.containsKey(key 1)) { result Math.max(result, map.get(key) map.get(key 1)); } } return result; } }4. 改进版hashmap就是把上面那个的两个for loop简化成一个for loop一遍put map的时候一边更新result。put完以后看看map里有没有比它大1或者小1的数字如果有就加上它的count。这里需要判断both 1和-1因为是按照原数组的排列顺序来的。也是O(n)Runtime: 59 ms, faster than 20.81% of Java online submissions for Longest Harmonious Subsequence.Memory Usage: 68 MB, less than 25.78% of Java online submissions for Longest Harmonious Subsequence.class Solution { public int findLHS(int[] nums) { int result 0; MapInteger, Integer map new HashMap(); for (int n : nums) { map.put(n, map.getOrDefault(n, 0) 1); if (map.containsKey(n 1)) { result Math.max(result, map.get(n) map.get(n 1)); } if (map.containsKey(n - 1)) { result Math.max(result, map.get(n) map.get(n - 1)); } } return result; } }
