2022/08/07

Leetcode Note: Go - Longest Harmonious Subsequence

Longest Harmonious Subsequence - LeetCode
https://leetcode.com/problems/longest-harmonious-subsequence/

  • Go 言語で取り組んだメモ

所感

  • Harmonious array: 最大値と最小値の差が 1 となる配列
  • int 配列 nums における最も長い Harmonious Subsequence の length を int で return する
  • Subsequence は残りの要素の順序を変更せずに、一部の要素を削除するかしないかで配列から生成できるシーケンスのこと

回答

Longest Harmonious Subsequence - LeetCode
https://leetcode.com/problems/longest-harmonious-subsequence/solution/

[Go] Map solution 48 ms - LeetCode Discuss
https://leetcode.com/problems/longest-harmonious-subsequence/discuss/559579/Go-Map-solution-48-ms

func findLHS(nums []int) int {
    numbers := make(map[int]int, len(nums))
    for _, n := range nums {
		numbers[n]++
	}
    ans := 0 
    for k, v := range numbers{
        if i, ok := numbers[k+1]; ok {
            ans = max(ans, i + v)
        }
    }
    
    return ans
}


func max(a,b int)int{
    if a > b{
        return a
    }

    return b
}
  • hash map で出現した数値と回数を管理
  • その後最大値を算出

See Also