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] <= 1090 <= 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