publicintfindLHS(int[] nums){ Arrays.sort(nums); int len = nums.length; int left = 0; int ans = 0; for (int right = 0; right < len; right++) { while (nums[right] - nums[left] > 1) { left++; }
if (nums[right] - nums[left] == 1) { ans = Math.max(ans, right - left + 1); } }
return ans; }
复杂度分析
时间复杂度:O(NlogN),其中 N 是数组 nums 的长度。因为需要对数组进行排序,花费的时间复杂度为 O(NlogN),然后利用双指针遍历数组花费的时间为 O(2N),总的时间复杂度 T(N)=O(NlogN)+O(2N)=O(NlogN)。
publicintfindLHS(int[] nums){ int len = nums.length; int ans = 0; Map<Integer, Integer> freq = new HashMap<>(); for (int x : nums) { freq.put(x, freq.getOrDefault(x, 0) + 1); }
Map<Integer, Integer> has = new HashMap<>(); for (int i = 0; i < len; i++) { has.put(nums[i], has.getOrDefault(nums[i], 0) + 1); if (freq.getOrDefault(nums[i] + 1, 0) == 0 && freq.getOrDefault(nums[i] - 1, 0) == 0) { continue; } int plus = freq.get(nums[i]) - has.get(nums[i]) + 1 + freq.getOrDefault(nums[i] + 1, 0) - has.getOrDefault(nums[i] + 1, 0); int minus = freq.get(nums[i]) - has.get(nums[i]) + 1 + freq.getOrDefault(nums[i] - 1, 0) - has.getOrDefault(nums[i] - 1, 0); ans = Math.max(ans, Math.max(plus, minus)); }
return ans; }
复杂度分析
时间复杂度:O(N),其中 N 是数组 nums 的长度。
空间复杂度:O(N),其中 N 是数组 nums 的长度,使用了 2 个 HashMap,因此空间复杂度度为 O(N)。
publicintfindLHS(int[] nums){ int ans = 0; Map<Integer, Integer> freq = new HashMap<>(); for (int x : nums) { freq.put(x, freq.getOrDefault(x, 0) + 1); }
for (int x : nums) { if (freq.getOrDefault(x + 1, 0) == 0 && freq.getOrDefault(x - 1, 0) == 0) { continue; } int plus = freq.get(x) + freq.getOrDefault(x + 1, 0); int minus = freq.get(x) + freq.getOrDefault(x - 1, 0); ans = Math.max(ans, Math.max(plus, minus)); }
publicintfindLHS(int[] nums){ int ans = 0; Map<Integer, Integer> freq = new HashMap<>(); for (int x : nums) { freq.put(x, freq.getOrDefault(x, 0) + 1); }
for (int key : freq.keySet()) { if (freq.containsKey(key + 1)) { int temp = freq.get(key) + freq.get(key + 1); ans = Math.max(ans, temp); } }
return ans; }
复杂度分析
时间复杂度:O(N),其中 N 是数组 nums 的长度。
空间复杂度:O(N),其中 N 是数组 nums 的长度,使用了 1 个 HashMap ,因此空间复杂度度为 O(N)。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)