【競技プログラミング】「Contains Duplicate 2」with Python | LeetCode #219

こちらは「Contains Duplicate 2」のPythonによる解答例となっております。この問題は、整数の配列と整数kが与えられたとき、配列内に重複する要素があり、その要素のインデックスの間がk以下である場合にTrueを返す問題です。

問題

整数の配列 nums と整数 k が与えられたとき、配列内に重複する要素があり、その要素のインデックスの間がk以下である場合にTrueを返します。

nums には、2つ以上の要素が含まれます。
10^5 <= nums.length <= 10^5
10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
答えは一意に定まります。

解法

この問題には、ハッシュマップを用いた1つのアプローチがあります。アルゴリズムの概要を以下に述べます。

ハッシュマップを初期化します。
配列を1つずつ反復処理します。
要素がハッシュマップに存在する場合、そのインデックスと現在のインデックスの差がk以下であるかどうかを確認します。
差がk以下である場合、Trueを返します。
存在しない場合、現在のインデックスをハッシュマップに追加します。
配列の反復処理が終了した場合、重複する要素がないことがわかります。Falseを返します。

Pythonコード

以下のコードが、「Contains Duplicate 2」を解くためのPythonプログラムとなります。

### Function ##################################################################

def solve(num=0):
    
    solver  = Solution().containsNearbyDuplicate
    
    if 1 <= num <= Input().input: id_LIST = [num]
    else: id_LIST = [id+1 for id in range(Input().input)]
    
    for id in id_LIST:
        data    = Input(id)
        ans     = solver(data.nums, data.k)
        result  = "OK" if ans==data.ans else "NG"
        print(f"[{str(id).zfill(3)}] {result}")

### Class #####################################################################

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        known = {}
        for id, num in enumerate(nums):
            if num in known: 
                if id - k <= known[num]: return True
            known[num] = id
        return False

#==============================================================================

class Input:
    
    def __init__(self, num=0):
        
        if num == 1:
            self.nums = [1,2,3,1]
            self.k = 3
            self.ans    = True
        
        elif num == 2:
            self.nums = [1,0,1,1]
            self.k = 1
            self.ans    = True

        elif num == 3:
            self.nums = [1,2,3,1,2,3]
            self.k = 2
            self.ans    = False
        
        else:
            self.input  = 3

### Main ######################################################################

if __name__ == "__main__":

    solve()

###############################################################################