숫자 리스트의 두개의 합이 특정 숫자가 되는지 검사하기

 

1. 숫자 리스트가 주어지고 숫자 k가 주어질때 숫자 리스트의 2개의 숫자의 합이 k가 되는지를 검사할 수 있는가?
2. 한번 훑으면서 할 수 있는가? (시간복잡도가 n인 상태로 할 수 있는가?)

 

int[] list = {10, 15, 3, 7};
int k = 17;

Set<Integer> hashSet = new HashSet<>();
for(int item : list) {
①	if(hashSet.contains(k-item)) return true;
②	hashSet.add(item);
}
return false;

 

숫자 리스트에서 한개씩 숫자를 꺼내서 O(1)의 시간복잡도로 검사하기 위해서

① HashSet을 사용하여 if문 안에서의 검색을 수행하고

② 만족하지 않으면 해당 내용을 add해서 O(1)의 시간복잡도로 HashSet에 추가하여

향상된 for문이 전체적으로 O(n)의 시간복잡도를 가질 수 있도록 구성