Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
Solution
Use hash_map [nums[i],i] to help
(Contains-Duplicate2.py) download 1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution ( object ):
def containsNearbyDuplicate ( self , nums , k ):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
hash_map = dict ()
for i in range ( len ( nums )):
idx = hash_map . get ( nums [ i ])
if idx >= 0 and k >= i - idx :
return True
hash_map [ nums [ i ]] = i
return False
(Contains-Duplicate2.java) download 1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public boolean containsNearbyDuplicate ( int [] nums , int k ) {
Map < Integer , Integer > hash_map = new HashMap < Integer , Integer >();
for ( int i = 0 ; i < nums . length ; i ++){
if ( hash_map . containsKey ( nums [ i ])){
if ( i - hash_map . get ( nums [ i ]) <= k ) return true ;
}
// 若nums[i]存在,但是i-hash_map.get(nums[i])>k, 也要更新hash_map
hash_map . put ( nums [ i ], i );
}
return false ;
}
}