두 포인터 알고리즘 설명

인터뷰에서 배열, 문자열, 연결 목록 등을 다룰 때 사용할 수 있는 간단하고 효과적인 기술을 설명하고 싶습니다. 이를 통해 이러한 데이터에 대한 기본 지식도 향상될 수 있습니다. 구조.

이론부터 시작해 보겠습니다. 이 알고리즘에는 두 가지 일반적인 사용 사례가 있습니다.

• 왼쪽/오른쪽 이 알고리즘의 중심 개념은 문자열이나 배열의 양쪽에서 이동하는 두 개의 정수 변수를 갖는 것입니다. 보통 사람들은 이를 왼쪽(left)과 오른쪽(right)이라고 부릅니다. 왼쪽은 인덱스 0에서 길이-1로 이동하고, 오른쪽은 그 반대입니다.

• 느린/빠른 포인터는 같은 방향(예: 처음부터 끝까지)으로 실행되지만 한 포인터는 다른 포인터보다 빠르게 실행됩니다. 이런 경우 사람들은 보통 변수를 느리고 빠르게 호출합니다.

알고리즘은 기본적이며 이를 이해하는 가장 좋은 방법은 몇 가지 예를 살펴보는 것입니다.

먼저 왼쪽 포인터와 오른쪽 포인터가 있는 경우를 살펴보겠습니다. 다음은 이 알고리즘을 사용하여 해결할 수 있는 문제의 기본 예입니다. 목표는 분명합니다. 합이 주어진 숫자와 같은 쌍을 찾는 것입니다.
무차별 대입 접근 방식은 중첩 루프를 생성하지만 이를 사용하여 인터뷰를 통과할 가능성은 낮습니다.
더 나은 접근 방식은 두 포인터 알고리즘을 사용하고 하나의 루프에서 O(n²) 대신 O(n) 복잡성을 갖는 것을 찾는 것입니다

const findPair = (arr, target) => {
    let left = 0;                 // Start with two pointers left from start, right, from the end
    let right = arr.length - 1;

    while (left < right) { // when pointers meet, finish loop
        const sum = arr[left] + arr[right];

        if (sum === target) {
            return [arr[left], arr[right]];  // Return the pair if we find the target sum
        } else if (sum < target) {
            left++;  // Move left pointer to the right if sum is less than target
        } else {
            right--;  // Move right pointer to the left if sum is greater than target
        }
    }

    return null;  // Return null if no such pair exists
}

const arr = [1, 2, 3, 4, 6];
const target = 6;

findPair(arr, target);  // Output: [2, 4]

포인터의 속도가 다른 접근 방식으로 전환해 보겠습니다. 면접으로 만날 수 있는 빈번한 문제입니다. 주어진 Linked List의 중간 부분을 찾아야 합니다.
무차별 접근 방식은 이전 예만큼 나쁘지는 않지만 면접관은 더 나은 접근 방식을 기대합니다.
2개의 포인터 알고리즘을 사용하면 O(n) 복잡성으로 이 문제를 해결할 수 있지만, 두 개의 순차 루프를 사용하는 경우 무차별 접근 방식에서는 O(2n)이 필요합니다.

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

const findMiddle = (head) => {
    if (!head) return null;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;           // Move slow pointer one step
        fast = fast.next.next;      // Move fast pointer two steps
    }

    return slow;  // Slow pointer will be at the middle
}

// Creating a linked list 1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);

head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

findMiddle(head).value);  // Output: 3 (middle node)

위 내용은 두 포인터 알고리즘 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!