LeetCode 219. Contains Duplicate II

はじめに

LeetCode 「219. Contains Duplicate II」の問題をGoで解きました。

問題

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

問題文

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

和訳
整数配列 nums と整数 k が与えられた場合、配列内に nums[i] == nums[j] かつ abs(i - j) <= k となる 2 つの異なるインデックス i と j が存在する場合は true を返します。

例

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

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

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

制約

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

解答1（HashMap）

重複する値を発見し、それぞれのインデックスの差がk以内であればtrueを返す問題です。
nums を走査しながら、各値の最新インデックスを記録すれば、1回のループで解けます。

コード

func containsNearbyDuplicate(nums []int, k int) bool {
    // i != j という条件を満たせないため、常に false
    if k == 0 {
        return false
    }

    lastSeenIndex := make(map[int]int)

    for i, v := range nums {
        index, exist := lastSeenIndex[v]
        if exist && (i - index) <= k {
            return true
        }
        lastSeenIndex[v] = i
    }

    return false
}

lastSeenIndexはnumsの値をキーとして、indexをバリューとして記録します。
existでキーの存在を判定し、存在している場合、差がk以内であればtrueを返しています。
それ以外の場合は、キーに対するバリューを更新しています。

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(n)

解答2（スライディングウィンドウ）

別のアプローチもあったので紹介します。
スライディングウィンドウを用いた方法です。

コード

func containsNearbyDuplicate(nums []int, k int) bool {
    // i != j という条件を満たせないため、常に false
    if k == 0 {
        return false
    }

    numSet := make(map[int]struct{})

    for i, v := range nums {
        if _, exist := numSet[v]; exist {
            return true
        }
        numSet[v] = struct{}{}

        if len(numSet) > k {
            delete(numSet, nums[i-k])
        }
    }

    return false
}

numSet := map[int]struct{}で要素の存在を記録します。
numSetをウィンドウとして は長さ k + 1 まで保持し、それを超えたら古い要素を削除します。
これは、ウィンドウ内の要素が k 以内の範囲に収まるようにするためです。
この方法では、インデックスは記録せずとも判定できます。

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(k)

numSet のサイズは最大で k 個までしか増えないため、最悪でも O(k) のメモリ使用量に収まります。
一方、HashMap を使う方法では、要素ごとに1回保存するので、最悪の場合 O(n) の空間を使うことになります。

参考

スライディングウィンドウを使用する別の問題を以下の記事で紹介しています。

• LeetCode 1652. Defuse the Bomb