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
}