LeetCode 594. Longest Harmonious Subsequence
はじめに
LeetCode 「594. Longest Harmonious Subsequence」の問題をGoで解きました。
問題
問題文
We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.
Given an integer array nums, return the length of its longest harmonious subsequence* among all its possible subsequences.
*A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
和訳
調和配列とは、最大値と最小値の差がちょうど 1 である配列と定義します。
整数配列 nums が与えられた場合、その配列に含まれる可能性のあるすべての部分列*の中で最も長い調和部分列の長さを返します。
*部分列は、残りの要素の順序を変更せずに、一部の要素を削除するか、要素をまったく削除しないことによって別の配列から派生できる配列です。
例
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation:
The longest harmonious subsequence is [3,2,2,2,3].
Input: nums = [1,2,3,4]
Output: 2
Explanation:
The longest harmonious subsequences are [1,2], [2,3], and [3,4], all of which have a length of 2.
Input: nums = [1,1,1,1]
Output: 0
Explanation:
No harmonic subsequence exists.
制約
- 1 <= nums.length <= 2 * 104
- -109 <= nums[i] <= 109
問題の理解
- 部分列 (subsequence): 順番を変えずに一部の要素を選ぶ（連続している必要はない）
- 調和のとれた部分列 (harmonious subsequence):
- 最も大きい要素と最も小さい要素の差が ちょうど 1
- その中で最も長い部分列の長さを求める
解答1（ソート・Two Pointers）
調和のとれた部分列を作るためには、ある数xとx+1のペアを選ぶ必要があります。
例1[1,3,2,2,5,2,3,7]だと2と3のペアが選ばれることになりますが、
ソートすると[1 2 2 2 3 3 5 7]となり、ある数xとx+1のペアの最大数をカウントしやすいです。
コード
func findLHS(nums []int) int {
// 配列をソートする
slices.Sort(nums)
maxLen := 0
left := 0
for right := 1; right < len(nums); right++ {
// 差が1より大きくなったらleftを調整
for nums[right]-nums[left] > 1 {
left++
}
// 調和のとれた部分列であるか確認
if nums[right]-nums[left] == 1 {
maxLen = max(maxLen, right-left+1)
}
}
return maxLen
}
// 最大値を求める関数
func max(a int, b int) int {
if a > b {
return a
}
return b
}
for文では、Two Pointers パターンを使って部分列の長さを求めています。
Two Pointersを使用した問題は、以下の記事でも扱っていますので参考にしてください。
計算量
- 時間的計算量：O(n log n)
- ソート: O(n log n)
- Two Pointers: O(n)
- 空間的計算量：O(1)
解答2（HashMap）
他にもアプローチがあったので紹介します。
HashMapを使い、それぞれの数値をカウントし、ある数xとx+1の最大数を求める方法です。
コード
func findLHS(nums []int) int {
// 数値の出現回数をカウント
freqMap := make(map[int]int)
for _, v := range nums {
freqMap[v]++
}
maxLen := 0
// 各キー x に対して x+1 の存在を確認し、最大長を更新
for key, count := range freqMap {
// key+1 が存在する場合のみ計算
if nextVal, exists := freqMap[key+1]; exists {
maxLen = max(maxLen, count+nextVal)
}
}
return maxLen
}
// 最大値を求める関数
func max(a int, b int) int {
if a > b {
return a
}
return b
}
まず、マップ (map[int]int) を使って各数字の出現回数をカウントします。
その後、key と key+1 のペアを探し、最大長を更新しています。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(n)
Discussion