[LeetCode] 220. Contains Duplicate III

😎풀이

1. 버킷 저장용 해시맵을 정의한다.
2. 버킷의 크기를 설정한다. (valueDiff를 기준으로 + 1 하여 동일한 버킷의 요소는 자동으로 valueDiff 조건이 만족됨)
3. nums를 순회한다.
   3-1. bucketKey를 현재 수 / bucketSize로 정의한다.
   3-2. 같은 bucketKey를 갖는 수가 있다면, 추후 indexDiff가 지나갈 경우 제거하는 로직이 있으므로 모든 조건을 만족하기에 true를 반환한다.
   3-3. 절댓값을 통해 검사하므로 이전/다음 버킷에 조건을 만족하는 수가 있을 수 있기에 bucketKey 기준 +-1에 해당하는 값들을 검사한다.
   3-4. 현재 값을 버킷에 추가한다.
   3-5. indexDiff 크기를 초과하는 요소를 제거한다.
4. 조건을 만족하는 경우가 없는 것이므로 false를 반환한다.

function containsNearbyAlmostDuplicate(nums: number[], indexDiff: number, valueDiff: number): boolean {
    const bucketMap = new Map<number, number>(); // 버킷을 저장할 해시맵
    const bucketSize = valueDiff + 1; // 버킷의 크기 설정

    for (let i = 0; i < nums.length; i++) {
        const bucketKey = Math.floor(nums[i] / bucketSize); // 현재 값이 속하는 버킷 키 계산

        // 현재 버킷에 이미 요소가 존재하면 조건 만족
        if (bucketMap.has(bucketKey)) return true;

        // 인접한 버킷(이전/다음)에 조건을 만족하는 숫자가 있는지 확인
        if (bucketMap.has(bucketKey - 1) && Math.abs(nums[i] - bucketMap.get(bucketKey - 1)!) <= valueDiff) return true;
        if (bucketMap.has(bucketKey + 1) && Math.abs(nums[i] - bucketMap.get(bucketKey + 1)!) <= valueDiff) return true;

        // 현재 값을 해당 버킷에 추가
        bucketMap.set(bucketKey, nums[i]);

        // indexDiff 크기를 초과하는 오래된 요소는 삭제
        if (i >= indexDiff) {
            const oldBucketKey = Math.floor(nums[i - indexDiff] / bucketSize);
            bucketMap.delete(oldBucketKey);
        }
    }

    return false;
}