◇ 알고리즘 정의
- 1차원 배열에서 각 다른 원소를 가르키는 2개의 포인터를 조작해가면서 원하는 값을 탐색하는 알고리즘이다.
◇ 알고리즘 동장방식
◇ 알고리즘 구현
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = {0, -5, -2, 4, 6, 9, -1};
int target = 5;
int count = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum < target) {
l++;
} else if (sum > target) {
r--;
} else {
count++;
l++;
r--;
}
}
}
System.out.println(count);
}
}
◇ 알고리즘 사용처
일반적으로 배열을 순회하며 연산을 할 때 투포인터 알고리즘을 사용하게 되면
(On^i)의 시간복잡도를 (On^(i-1))로 줄일 수 있다.
'Java & Spring > 알고리즘' 카테고리의 다른 글
그래프탐색 - DFS와 BFS (0) | 2024.12.23 |
---|---|
에라토스테네스의 체(소수, 약수 구하기) (0) | 2024.07.26 |
유클리드 호제법(최대공약수 구하기) (0) | 2024.07.18 |