【海外エンジニア転職 Coding Interview鍛錬】LeetCode 217. Contains Duplicate

こんにちは脳筋ニシキです！

今回もこちらで紹介したLeetCode75選（Blind75）から１問（easy）選んで解いていきたいと思います！
atsashimipy.hatenablog.com

今回解いていくのはこちらの問題

217. Contains Duplicate

被ってる？

やること

整数の配列 nums が与えられたとき、いずれかの値が配列中に少なくとも2個ある時Trueを返し、 すべての要素が異なる場合はFalseを返す。

条件

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

例

Input: nums = [1,2,3,1]
Output: True

Input: nums = [1,2,3,4]
Output: False

カテゴリ

Arrays

考え方

配列を一巡する過程で、要素を記録かつその記録された要素を参照。Memoizationの考え方
atsashimipy.hatenablog.com

もし、その要素が記録にあれば、True。

早速解いていく!

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:

出現した要素を記録するmemoを設定

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        memo = set()

ここでset()を使ったのは、参照にかかる負担を減らすため。

for loop で要素を一つ一つチェックしていく

今まで見たことない要素であれば、memoに記録し、
memo内に存在するのであれば その時点でTrue を返す。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        memo = set()
        
        for i in nums:
            if i not in memo:
                memo.add(i)
            else:
                return True

最後までダブり要素がなかった場合 False を返す。

解答例

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        memo = set()
        
        for i in nums:
            if i not in memo:
                memo.add(i)
            else:
                return True
            
        return False

Complexity Analysis

Time complexity : O(n)

N回づつ参照し、記録。

Space complexity : O(n)

setのサイズは線形に増加

おまけ

おそらく問題の意図から反してしまうが、

set()を使ってこうも解ける。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        
        if len(nums) != len(set(nums)):
            return True
        else:
            return False

set()はユニークな要素しか含まないので、ダブりがあった場合もとのnumsより短くなる。

みんなユニークでみんな良い

誰かの参考になって来れば幸いです！
それではまた次のLeetCodeで！
ありがとうございましたー！