(C++) - LeetCode (easy) 219. Contains Duplicate II

https://leetcode.com/problems/contains-duplicate-ii/description/

Contains Duplicate II - LeetCode

자료구조를 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

key에는 nums원소, value에는 index를 저장하는 map m을 선언합니다.

📔 풀이과정

2차원 for loop로는 시간초과가 납니다. 최대 10만개가 nums size로 가능하기 때문에 nlogn의 시간복잡도로 푸는 것이 이상적입니다. 

nums 원소를 순회하며 원소와 해당 index를 m에 넣다가 key 값이 같은 경우 공식을 적용해 k보다 작다면 바로 true를 반환합니다.

---

📕 Code

📔 C++

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

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.