219. Contains Duplicate II

Easy

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.

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

Constraints:

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

• 0 <= k <= 105

解題

第一種方法，不使用map，需時1563ms

func containsNearbyDuplicate(nums []int, k int) bool {
    for i:=0; i<len(nums); i++ {
        for j:=i+1; j<=i+k && j<len(nums); j++ {
            if nums[i]==nums[j] {
                return true
            }
        }
    }
    
    return false
}

第二種方法，使用map，只要144ms

func containsNearbyDuplicate(nums []int, k int) bool {
    count := make(map[int]int)
    
    for index, val := range nums {
        if last_index, ok := count[val]; ok {
            if index-last_index <= k {
                return true
            } 
        }
        count[val] = index
    }
    
    return false
}