투포인터란?
투 포인터(Two Pointers)는 두 개의 포인터를 이용하여 배열 또는 리스트를 탐색하는 알고리즘이다. 보통 배열의 왼쪽 끝과 오른쪽 끝을 가리키는 두 개의 포인터를 이용하여 구현한다. 배열이 정렬 돼 있을 때 사용하면 좋은 알고리즘이다.
위의 이미지를 자바스크립트 코드로 나타내보자.
function twoSum(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum <br target) {
left++;
} else {
right--;
}
}
return [];
}
const nums = [1, 5, 8, 10, 13, 16, 27, 32, 45, 60];
const target = 40;
const result = twoSum(nums, target);
console.log(result); // [2, 7]
- left와 right로 배열의 양 끝을 저장해준다
- left와 right를 더해서 sum이란 변수를 만들어준다
- sum이 target보다 작으면 left를 오른쪽으로 이동
- sum이 target보다 크면 right를 왼쪽으로 이동
- sum이 target과 같으면 값을 리턴해준다.
이미지 출처
https://tarunjain07.medium.com/two-pointers-notes-4d1400357437