Given an array of integers nums and an integer k, determine whether there are two distinct indices i and j in the array where nums[i] = nums[j] and the absolute difference between i and j is less than or equal to k.

Example

• For nums = [0, 1, 2, 3, 5, 2] and k = 3, the output should be

  solution(nums, k) = true.

  There are two **2**s in nums, and the absolute difference between their positions is exactly 3.

• For nums = [0, 1, 2, 3, 5, 2] and k = 2, the output should be

  solution(nums, k) = false.

  The absolute difference between the positions of the two **2**s is 3, which is more than k.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer nums

  Guaranteed constraints:

  0 ≤ nums.length ≤ 55000,

  • 231 - 1 ≤ nums[i] ≤ 231 - 1.

• [input] integer k

  Guaranteed constraints:

  0 ≤ k ≤ 35000.

• [output] boolean

풀이

boolean solution(int[] nums, int k) {
    // 요소와 해당 인덱스를 저장할 해시맵을 생성
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        
        // 현재 요소가 해시맵에 이미 존재하는지 확인
        if (map.containsKey(num)) {
            // 인덱스 간의 절대 차이가 k 이하인지 확인. 그렇다면 true를 반환.
            if (i - map.get(num) <= k) {
                return true;
            }
        }
        
        // 현재 요소에 대한 해시맵의 인덱스를 업데이트.
        map.put(num, i);
    }

    // 이 조건을 만족하는 쌍을 찾지 못하면 false를 반환.
    return false;
}