https://www.youtube.com/watch?v=cxhbgAbAiXI&list=PLcXyemr8ZeoTVBFTEB673TC8Ba4UBSTRz&index=6
리스트에 있는 서로 다른 두 정수의 합이 target number와 같다면 true를 반환하는 함수를 구현하시오.
리스트에 있는 서로 다른 두 정수의 합이 target number와 같다면 true를 반환하는 함수를 구현하시오.
입력값
num = {1, 2, 15, 6} target Number = 7
num = {1, 2, 15, 6} target Number = 7
public static boolean twoSum(){
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums.length;j++){
if( i == j ) continue;
int sum = nums[i] + nums[j];
if( sum == target )
return True;
}
}
return false;
}시간복잡도는 O(N^2) 이다.
위의 코드를 개선해보자.
num = {1, 2, 15, 6} target Number = 7
public static boolean twoSum(){
for(int i=0;i<nums.length;i++){
for(int j=i + 1;j<nums.length;j++){
int sum = nums[i] + nums[j];
if( sum == target )
return True;
}
}
return false;
}개선은 되었지만, 시간복잡도는 O(N^2) 이다.
성능자체는 개선되었다.
HashSet을 활용한다면 훨씬 빨라질것이다.
num = {1, 2, 15, 6} target Number = 7
public static boolean twoSum(){
for(int i=0;i<nums.length;i++){
hashset.add(nums[i]);
}
for(int i=0;i<nums.length;i++){
if( hashset.contains( targetNumber - nums[i] ) == true ){
return true;
}
}
return false;
}
시간복잡도는 O(N) 이다.
HashSet 사용시 시간복잡도 조회는 O(1)이다.
문제가 있다. 코드에는 버그가 잇다.
만약 target Numbers = 4 이다.
1 2 15 6 .. 에서 만약
만약 2 를 선택했을경우 똑같은 2 가 두번 계산되서 오류가 난다. 문제의 조건은 서로 다른 두 정수인것이다.
num = {1, 2, 15, 6} target Number = 4
public static boolean twoSum(){
Hashset hashset = new HashSet<>();
for(int i=0;i<nums.length;i++){
if( hashset.contains( targetNumber - nums[i] ) == true ){
return true;
} else{
hashset.add(numbs[i]);
}
}
return false;
}
이를 통해 중복된 값을 연산하지 않고, 이전까지의 숫자 값에서 targetNumber와 같은 값을 알아낼 수 있다.
시간복잡도는, Set만드는작업은 O(1), for문은 N번 반복되고 바디부분에서의 시간복잡도는 O(1)이다.
즉, O(1) + N * O(1) 이므로 O(N) 이다.