LeetCodeを1日1題解いてみる (day45)

45日目に取り組んだ問題はこちら！

594. Longest Harmonious Subsequence

問題文

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.

僕の回答

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums_sorted = sorted(nums)
        count_dict = {}
        prev_count = 1
        max_leng = 0
        prev_val = nums_sorted[0]
        for n in nums_sorted[1:]:
            if prev_val != n:
                count_dict[prev_val] = prev_count
                if prev_val - 1 in count_dict:
                    max_leng = max(
                        max_leng,
                        count_dict[prev_val]+count_dict[prev_val-1],
                    )
                prev_count = 0
                prev_val = n
            prev_count += 1
        count_dict[prev_val] = prev_count
        if prev_val - 1 in count_dict:
            max_leng = max(
                max_leng,
                count_dict[prev_val]+count_dict[prev_val-1],
            )
        return max_leng

より効率の良い回答例

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        count = Counter(nums)
        largest_count = 0
        for key in count:
            if (key + 1) in count:
                largest_count = max(largest_count, (count[key] + count[key + 1]))
        
        return largest_count

学んだこと

• Counter(nums): Pythonの標準ライブラリcollectionsに含まれる Counterクラスを使って、リストや文字列の要素ごとの出現回数を数えるためのもの

コメント

とても時間がかかった。実装方針は回答例と同じだから複雑にはなってしまったけど、良かったと思う。

次の問題はこちら!