(Leet Code c++)Contains Duplicate(2)

219. Contains Duplicate II

 

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을 이용해 문제 풀이.

nums를 순회하면서 해당 원소가 map에 들어있는지 우선 확인한다.

[] 를 이용하면 0으로 초기화되기 때문에 map의 find()를 이용했다.

 

find()가 m.end()와 같다면 map에 해당 원소가 없다는 뜻이기 때문에 해당 원소의 위치를 넣어주도록 한다.

 

만약 map에 해당 원소가 있다면 두 수의 위치 차이가 k 이하인지 확인한다.

두 수의 위치 차이가 k 이하라면 바로 true를 리턴하여 종료.

 

아니라면 num[i]의 위치를 갱신해주도록 한다.

 

for문을 빠져나오게 되면 중복되는 값의 위치가 k 이하가 아니기 때문에 false를 리턴

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> m;
        
        for(int i = 0; i < nums.size(); i++){
            if(m.find(nums[i]) == m.end()){
                m[nums[i]] = i;
            }
            else{
                if(abs(m[nums[i]] - i) <= k){
                    return true;
                }
                else{
                    m[nums[i]] = i;
                }
            }
        }
        
        return false;
    }
};