Contains Duplicate II

,

Problem

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 absolute difference between i and j is at most k.

Example 1

1
2

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2

1
2

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3

1
2

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

My Answer ( Use HashMap )

  • HashMap을 이용하자.
  • nums를 순회하면서, nums[i]를 HashMap의 키로, index를 값으로 할당하자.
  • 만약 nums[i]가 Hashmap의 키로 존재하면서, 현재 index - 해당 값이 k보다 같거나 작으면 true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hashmap = new HashMap<>();
        
        for(int i=0;i<nums.length;i++) {
            if ( hashmap.containsKey(nums[i])) {
                if ( i - hashmap.get(nums[i]) <= k ) {
                    return true;                
                } 
            }
            
            hashmap.put(nums[i], i);    
        }
        
        return false;
    }
}

My Answer

  • index l,r을 이용해서, nums[l]과 nums[r]을 비교해서 알아내자.
  • 만약 r-l이 k랑 같거나, r이 nums.length - 1과 같다면, l을 증가 시키자.
  • 그렇지 않다면 r을 증가 시키자.
  • 이런식으로 비교 하다가 nums[l]과 nums[r]이 같아지면 true이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if ( k == 0 ) return false; 
        
        int l=0;
        int r=0;
        
        while( l < nums.length -1 ) {            
            if ( l != r && nums[l] == nums[r] ) return true;
            
            if ( r-l == k || r == nums.length -1 ) {
                l++;                
            } else {
                r++;
            }            
        }
        
        return false;
    }
}

참고