[LeetCode] Find All K-Distant Indices in an Array (JAVA)

https://leetcode.com/problems/find-all-k-distant-indices-in-an-array/?envType=daily-question&envId=2025-06-24

 

해당 문제는 단순히 이중for문을 통해서 각 배열의 요소가 k거리이내에 key값이 존재하는지 검사하는 방식만으로도 충분히 해결이 가능한 문제입니다.

 

하지만 위 방식으로는 다소 비효율적인 부분이 발생하게 됩니다.

위와 같은 경우에 주어진 범위내에 key값이 존재하는지 검사하면서 아래와 같이 동일한 구간을 중복으로 검사하게되는 상황이 발생하게됩니다.

 

 

또한 key값을 기준으로 k범위 내의 자리를 추가하는 방식또한 아래와 같은 중복이 발생하게됩니다. 

 

때문에 위와같은 중복현상을 해결하기위해서 Two Pointer 개념을 도입하여 중복을 해결하기로했습니다.

 

위와 같은 케이스를 예시로보면 

 

첫번째 key값을 만났을때(cur) k범위만큼 start, end값을 지정해주고 각 위치를 추가해줍니다. 

 

이후 다음 key값을 만났을때는 start의 값을 이전의 end값과 현재의 start값을 비교해서 더 큰 값을 start값으로 지정해주면 됩니다.

즉, end값의 상태를 계속 유지하면서 start 값을 정하는 방식으로 중복문제를 해결할수있게됩니다.

 

import java.util.ArrayList;
import java.util.List;

public class Solution {
	public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
		int start = 0, end = 0;
		List<Integer> result = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			if(nums[i] == key){
				start = Math.max(end, i-k);
				end = Math.min(i+k, nums.length)+1;
				for (int j = start; j < end; j++) {
					result.add(j);
				}
			}
		}
		return result;
	}
}