LeetCode / Contains Duplicate, Contains Duplicate Ⅱ

明日から海外旅行で浮き足立っていますが、リストから重複判定する問題シリーズを解きます。

https://leetcode.com/problems/contains-duplicate/

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:
Input: [1,2,3,1]
Output: true

Example 2:
Input: [1,2,3,4]
Output: false

Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

リスト中に重複があればTrueを返す問題。これは簡単。

解法1

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

これだけでは物足りないのでもう一問。

https://leetcode.com/problems/contains-duplicate-ii/

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

問題文の英語がわかるかどうかが勝負。インデックスi, jについて、nums[i] = nums[j]となり、かつiとjの差がk以下の要素があればTrueを返す問題。

解法1

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        dic = {}
        for i, n in enumerate(nums):
            if n in dic and i - dic[n] <= k:
                return True
            dic[n] = i
        return False