public int findLHS(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int start = 0;
int min = nums[0];
int res = 0;
int nextstart = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i]  min > 1) {
start = nextstart++;
min = nums[start];
i;
} else if (nums[i]  min == 1) {
res = Math.max(res, i  start + 1);
if (nums[i] != nums[i  1]) {
nextstart = i;
}
}
}
return res;
}
Simple Java Sort Solution (beat 100%)


@johnyrufus16 Thanks for your comment. I optimized the code. Now it runs in 44 ms and beats 100%. Actually if we need to move start idx, we can't make it point to i directly. We need to use a variable to keep track of the next idx. Example would be 1, 1, 1, 2, 2, 3, 3, in this case, if i points to 3 where the idx is 5, we should change start idx to point to first 2's idx which is 3.

@ihaveayaya
nice, you have optimized a lot, but we can still proceed in a fashion where stardIdx never needs to go back, here is my code (my code ooks a bit more stressful :) so not sure if its worth the effort):public static int findLHS(int[] nums) { if(nums.length < 2 ) return 0; Arrays.sort(nums); int count = 0; int res = Integer.MIN_VALUE; int curi = 0; int curj = 0; while(curj + 1 < nums.length && nums[curj + 1] == nums[0]) ++curj; for(int nexti = curj+1; nexti < nums.length; nexti++) { int nextj = nexti; while(nextj + 1 < nums.length && nums[nextj + 1] == nums[nexti]) ++nextj; if(nums[curi] + 1 == nums[nexti]) { res = Math.max(res, nextj  curi + 1); } curi = nexti; curj = nextj; nexti = curj; } return Math.max(res, count); }

@johnyrufus16 Thanks for your post. I have already changed the way to traverse the array. Start idx now always increase.

@daniexia I think it's test case specific. Hashmap can introduce some overhead which would slow down the execution. We are not comparing runtime complexity here.

public class Solution { public int findLHS(int[] nums) { Arrays.sort(nums); int result = 0; int left = 0, right = 0; while (right < nums.length) { if (nums[right]  nums[left] < 1) right++; else if (nums[right]  nums[left] == 1) { result = Math.max(result, right  left + 1); right++; } else left++; } return result; } }

my code beats >94%
public class Solution { public int findLHS(int[] nums) { if(nums == null  nums.length <= 1){ return 0; } Arrays.sort(nums); int len = nums.length; int max = 0; int curr = 0; int small = 1; int large = 0; //分情况讨论：1.如果当前元素等于前一个元素（再继续判断它是属于小的还是大的） //2.如果当前元素值比前一个元素值大1（判断该元素是下一次比较的较大者，还是本次比较的较大者） //3.如果不符合上面两种情况，则重置large和small //每一轮比较，如果large不为0的话，说明有存在值相差1的序列对，则更新max的值 for(int i = 1; i < len; i++){ if(nums[i] == nums[i1] + 1){ if(small == 0){ small = 1; }else if(large != 0){ max = Math.max(max, large+small); small = large; } large = 1; }else if(nums[i] == nums[i1]){ if(large == 0){ small++; }else{ large++; } }else{ small = 1; large = 0; } if(large != 0){ max = Math.max(max, large+small); } } return max; } }

My clean version:
public int findLHS(int[] nums) { int result = 0; Arrays.sort(nums); int left = 0 , right = 1; //right is the subsequence's right RHS index and left is the subsequence's LHS index //namely: nums[right] is max, nums[left] is min while(right<nums.length){ while(nums[right]nums[left]>1) left++; //in case of difference between max and min > 1 if(rightleft+1>result&&nums[right]nums[left]==1) result = rightleft+1; //update result if new length: rightleft+1> result and difference between max and min = 1 right++; } return result; }