Leetcode - 219. Contains Duplicate II

문제

배열이 주어지고 서로다른 두 인덱스 i, j가 있을때 다음의 조건을 만족하는 i,j가 있다면 true 리턴
nums[i] == nums[j] abs(i - j) <= k.

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

문제를 다시 해석하면 i, j의 간격크기가 k 이하인 요소 중, 배열값이 서로 같은 요소가 있는지 확인하는것과 같음.

해결 O(N)

sliding window와 hashtable을 활용한 풀이. 먼저 초기 윈도우사이즈 k만큼 해시테이블에 빈도수를 기록하고, 그뒤 윈도우를 이동하면서 바뀐부분(이전 윈도우의 첫번째, 다음윈도우의 마지막)만 체크하면 해결된다. 빈도수가 2가되면 true다.
마지막으로 처음으로 C로 hashtable을 구현하지 않고 cpp의 unordered_map을 사용했는데, 그렇게 간편할수가 없다. leetcode에서 처음으로 stl을 사용해서 풀었는데, c++로 전환준비중인 요즘이라 더 기쁘다.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        std::unordered_map<int, int> table;
        int nsize = nums.size();
        
        for (int i = 0; i <= k && i < nsize; i++) {
            if (i < nsize && table[nums[i]] > 0)
                return true;
            table[nums[i]]++;
        }
        for (int i = 0; i+k+1 < nsize; i++) {
            table[nums[i]]--;
            if (table[nums[i+k+1]] > 0)
                return true;
            table[nums[i+k+1]]++;
        }
        return false;
    }
};

해결 O(N^2)

무지성방식, TLE 발생

/* brute force : Time Limit Exceeded */
bool containsNearbyDuplicate(int* nums, int numsSize, int k){
    for (int i = 0; i < numsSize; i++) {
        for (int j = i+1; j < numsSize && j < i+k+1; j++) {
            if (nums[i] == nums[j] && abs(i-j) <= k)
                return true;
        }
    }
    return false;
}