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
}
Last modified 11mo ago