Skip to content

Commit dba96c4

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problem: No.0594 (doocs#3173)
No.0594.Longest Harmonious Subsequence
1 parent 6e1823a commit dba96c4

File tree

8 files changed

+125
-128
lines changed

8 files changed

+125
-128
lines changed

‎solution/0500-0599/0594.Longest Harmonious Subsequence/README.md

Lines changed: 44 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,11 @@ tags:
6565

6666
<!-- solution:start -->
6767

68-
### 方法一
68+
### 方法一：哈希表
69+
70+
我们可以用一个哈希表 $\text{cnt}$ 记录数组 $\text{nums}$ 中每个元素出现的次数，然后遍历哈希表中的每个键值对 $(x, c)$，如果哈希表中存在键 $x + 1$，那么 $\text{nums}$ 中元素 $x$ 和 $x + 1$ 出现的次数之和 $c + \text{cnt}[x + 1]$ 就是一个和谐子序列，我们只需要在所有和谐子序列中找到最大的长度即可。
71+
72+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\text{nums}$ 的长度。
6973

7074
<!-- tabs:start -->
7175

@@ -74,27 +78,24 @@ tags:
7478
```python
7579
class Solution:
7680
def findLHS(self, nums: List[int]) -> int:
77-
ans = 0
78-
counter = Counter(nums)
79-
for num in nums:
80-
if num + 1 in counter:
81-
ans = max(ans, counter[num] + counter[num + 1])
82-
return ans
81+
cnt = Counter(nums)
82+
return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)
8383
```
8484

8585
#### Java
8686

8787
```java
8888
class Solution {
8989
public int findLHS(int[] nums) {
90-
Map<Integer, Integer> counter = new HashMap<>();
91-
for (int num : nums) {
92-
counter.put(num, counter.getOrDefault(num, 0) + 1);
90+
Map<Integer, Integer> cnt = new HashMap<>();
91+
for (int x : nums) {
92+
cnt.merge(x, 1, Integer::sum);
9393
}
9494
int ans = 0;
95-
for (int num : nums) {
96-
if (counter.containsKey(num + 1)) {
97-
ans = Math.max(ans, counter.get(num) + counter.get(num + 1));
95+
for (var e : cnt.entrySet()) {
96+
int x = e.getKey(), c = e.getValue();
97+
if (cnt.containsKey(x + 1)) {
98+
ans = Math.max(ans, c + cnt.get(x + 1));
9899
}
99100
}
100101
return ans;
@@ -108,14 +109,14 @@ class Solution {
108109
class Solution {
109110
public:
110111
int findLHS(vector<int>& nums) {
111-
unordered_map<int, int> counter;
112-
for (int num : nums) {
113-
++counter[num];
112+
unordered_map<int, int> cnt;
113+
for (int x : nums) {
114+
++cnt[x];
114115
}
115116
int ans = 0;
116-
for (int num : nums) {
117-
if (counter.count(num + 1)) {
118-
ans = max(ans, counter[num] + counter[num + 1]);
117+
for (auto& [x, c] : cnt) {
118+
if (cnt.contains(x + 1)) {
119+
ans = max(ans, c + cnt[x + 1]);
119120
}
120121
}
121122
return ans;
@@ -126,41 +127,37 @@ public:
126127
#### Go
127128
128129
```go
129-
func findLHS(nums []int) int {
130-
counter := make(map[int]int)
131-
for _, num := range nums {
132-
counter[num]++
130+
func findLHS(nums []int) (ans int) {
131+
cnt := map[int]int{}
132+
for _, x := range nums {
133+
cnt[x]++
133134
}
134-
ans := 0
135-
for _, num := range nums {
136-
if counter[num+1] > 0 {
137-
ans = max(ans, counter[num]+counter[num+1])
135+
for x, c := range cnt {
136+
if c1, ok := cnt[x+1]; ok {
137+
ans = max(ans, c+c1)
138138
}
139139
}
140-
return ans
140+
return
141141
}
142142
```
143143

144-
<!-- tabs:end -->
145-
146-
<!-- solution:end -->
147-
148-
<!-- solution:start -->
149-
150-
### 方法二
151-
152-
<!-- tabs:start -->
144+
#### TypeScript
153145

154-
#### Python3
155-
156-
```python
157-
class Solution:
158-
def findLHS(self, nums: List[int]) -> int:
159-
counter = Counter(nums)
160-
return max(
161-
[counter[num] + counter[num + 1] for num in nums if num + 1 in counter],
162-
default=0,
163-
)
146+
```ts
147+
function findLHS(nums: number[]): number {
148+
const cnt: Record<number, number> = {};
149+
for (const x of nums) {
150+
cnt[x] = (cnt[x] || 0) + 1;
151+
}
152+
let ans = 0;
153+
for (const [x, c] of Object.entries(cnt)) {
154+
const y = +x + 1;
155+
if (cnt[y]) {
156+
ans = Math.max(ans, c + cnt[y]);
157+
}
158+
}
159+
return ans;
160+
}
164161
```
165162

166163
<!-- tabs:end -->

‎solution/0500-0599/0594.Longest Harmonious Subsequence/README_EN.md

Lines changed: 44 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,11 @@ tags:
7878

7979
<!-- solution:start -->
8080

81-
### Solution 1
81+
### Solution 1: Hash Table
82+
83+
We can use a hash table $\text{cnt}$ to record the occurrence count of each element in the array $\text{nums}$. Then, we iterate through each key-value pair $(x, c)$ in the hash table. If the key $x + 1$ exists in the hash table, then the sum of occurrences of elements $x$ and $x + 1$, $c + \text{cnt}[x + 1]$, forms a harmonious subsequence. We just need to find the maximum length among all harmonious subsequences.
84+
85+
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\text{nums}$.
8286

8387
<!-- tabs:start -->
8488

@@ -87,27 +91,24 @@ tags:
8791
```python
8892
class Solution:
8993
def findLHS(self, nums: List[int]) -> int:
90-
ans = 0
91-
counter = Counter(nums)
92-
for num in nums:
93-
if num + 1 in counter:
94-
ans = max(ans, counter[num] + counter[num + 1])
95-
return ans
94+
cnt = Counter(nums)
95+
return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)
9696
```
9797

9898
#### Java
9999

100100
```java
101101
class Solution {
102102
public int findLHS(int[] nums) {
103-
Map<Integer, Integer> counter = new HashMap<>();
104-
for (int num : nums) {
105-
counter.put(num, counter.getOrDefault(num, 0) + 1);
103+
Map<Integer, Integer> cnt = new HashMap<>();
104+
for (int x : nums) {
105+
cnt.merge(x, 1, Integer::sum);
106106
}
107107
int ans = 0;
108-
for (int num : nums) {
109-
if (counter.containsKey(num + 1)) {
110-
ans = Math.max(ans, counter.get(num) + counter.get(num + 1));
108+
for (var e : cnt.entrySet()) {
109+
int x = e.getKey(), c = e.getValue();
110+
if (cnt.containsKey(x + 1)) {
111+
ans = Math.max(ans, c + cnt.get(x + 1));
111112
}
112113
}
113114
return ans;
@@ -121,14 +122,14 @@ class Solution {
121122
class Solution {
122123
public:
123124
int findLHS(vector<int>& nums) {
124-
unordered_map<int, int> counter;
125-
for (int num : nums) {
126-
++counter[num];
125+
unordered_map<int, int> cnt;
126+
for (int x : nums) {
127+
++cnt[x];
127128
}
128129
int ans = 0;
129-
for (int num : nums) {
130-
if (counter.count(num + 1)) {
131-
ans = max(ans, counter[num] + counter[num + 1]);
130+
for (auto& [x, c] : cnt) {
131+
if (cnt.contains(x + 1)) {
132+
ans = max(ans, c + cnt[x + 1]);
132133
}
133134
}
134135
return ans;
@@ -139,41 +140,37 @@ public:
139140
#### Go
140141
141142
```go
142-
func findLHS(nums []int) int {
143-
counter := make(map[int]int)
144-
for _, num := range nums {
145-
counter[num]++
143+
func findLHS(nums []int) (ans int) {
144+
cnt := map[int]int{}
145+
for _, x := range nums {
146+
cnt[x]++
146147
}
147-
ans := 0
148-
for _, num := range nums {
149-
if counter[num+1] > 0 {
150-
ans = max(ans, counter[num]+counter[num+1])
148+
for x, c := range cnt {
149+
if c1, ok := cnt[x+1]; ok {
150+
ans = max(ans, c+c1)
151151
}
152152
}
153-
return ans
153+
return
154154
}
155155
```
156156

157-
<!-- tabs:end -->
158-
159-
<!-- solution:end -->
160-
161-
<!-- solution:start -->
162-
163-
### Solution 2
164-
165-
<!-- tabs:start -->
157+
#### TypeScript
166158

167-
#### Python3
168-
169-
```python
170-
class Solution:
171-
def findLHS(self, nums: List[int]) -> int:
172-
counter = Counter(nums)
173-
return max(
174-
[counter[num] + counter[num + 1] for num in nums if num + 1 in counter],
175-
default=0,
176-
)
159+
```ts
160+
function findLHS(nums: number[]): number {
161+
const cnt: Record<number, number> = {};
162+
for (const x of nums) {
163+
cnt[x] = (cnt[x] || 0) + 1;
164+
}
165+
let ans = 0;
166+
for (const [x, c] of Object.entries(cnt)) {
167+
const y = +x + 1;
168+
if (cnt[y]) {
169+
ans = Math.max(ans, c + cnt[y]);
170+
}
171+
}
172+
return ans;
173+
}
177174
```
178175

179176
<!-- tabs:end -->

‎solution/0500-0599/0594.Longest Harmonious Subsequence/Solution.cpp

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,14 @@
11
class Solution {
22
public:
33
int findLHS(vector<int>& nums) {
4-
unordered_map<int, int> counter;
5-
for (int num : nums) {
6-
++counter[num];
4+
unordered_map<int, int> cnt;
5+
for (int x : nums) {
6+
++cnt[x];
77
}
88
int ans = 0;
9-
for (int num : nums) {
10-
if (counter.count(num + 1)) {
11-
ans = max(ans, counter[num] + counter[num + 1]);
9+
for (auto& [x, c] : cnt) {
10+
if (cnt.contains(x + 1)) {
11+
ans = max(ans, c + cnt[x + 1]);
1212
}
1313
}
1414
return ans;

‎solution/0500-0599/0594.Longest Harmonious Subsequence/Solution.go

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,12 @@
1-
func findLHS(nums []int) int {
2-
counter := make(map[int]int)
3-
for _, num := range nums {
4-
counter[num]++
1+
func findLHS(nums []int) (ans int) {
2+
cnt := map[int]int{}
3+
for _, x := range nums {
4+
cnt[x]++
55
}
6-
ans := 0
7-
for _, num := range nums {
8-
if counter[num+1] > 0 {
9-
ans = max(ans, counter[num]+counter[num+1])
6+
for x, c := range cnt {
7+
if c1, ok := cnt[x+1]; ok {
8+
ans = max(ans, c+c1)
109
}
1110
}
12-
return ans
11+
return
1312
}

‎solution/0500-0599/0594.Longest Harmonious Subsequence/Solution.java

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,14 @@
11
class Solution {
22
public int findLHS(int[] nums) {
3-
Map<Integer, Integer> counter = new HashMap<>();
4-
for (int num : nums) {
5-
counter.put(num, counter.getOrDefault(num, 0) + 1);
3+
Map<Integer, Integer> cnt = new HashMap<>();
4+
for (int x : nums) {
5+
cnt.merge(x, 1, Integer::sum);
66
}
77
int ans = 0;
8-
for (int num : nums) {
9-
if (counter.containsKey(num + 1)) {
10-
ans = Math.max(ans, counter.get(num) + counter.get(num + 1));
8+
for (var e : cnt.entrySet()) {
9+
int x = e.getKey(), c = e.getValue();
10+
if (cnt.containsKey(x + 1)) {
11+
ans = Math.max(ans, c + cnt.get(x + 1));
1112
}
1213
}
1314
return ans;

‎solution/0500-0599/0594.Longest Harmonious Subsequence/Solution.py

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,4 @@
11
class Solution:
22
def findLHS(self, nums: List[int]) -> int:
3-
ans = 0
4-
counter = Counter(nums)
5-
for num in nums:
6-
if num + 1 in counter:
7-
ans = max(ans, counter[num] + counter[num + 1])
8-
return ans
3+
cnt = Counter(nums)
4+
return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)

‎solution/0500-0599/0594.Longest Harmonious Subsequence/Solution.ts

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
function findLHS(nums: number[]): number {
2+
const cnt: Record<number, number> = {};
3+
for (const x of nums) {
4+
cnt[x] = (cnt[x] || 0) + 1;
5+
}
6+
let ans = 0;
7+
for (const [x, c] of Object.entries(cnt)) {
8+
const y = +x + 1;
9+
if (cnt[y]) {
10+
ans = Math.max(ans, c + cnt[y]);
11+
}
12+
}
13+
return ans;
14+
}

‎solution/0500-0599/0594.Longest Harmonious Subsequence/Solution2.py

Lines changed: 0 additions & 7 deletions
This file was deleted.

0 commit comments

Comments
 (0)