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

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

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

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

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

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

포인터의 속도가 다른 접근 방식으로 전환해 보겠습니다. 면접으로 만날 수 있는 빈번한 문제입니다. 주어진 Linked List의 중간 부분을 찾아야 합니다.

무차별 접근 방식은 이전 예만큼 나쁘지는 않지만 면접관은 더 나은 접근 방식을 기대합니다.

두 포인터 알고리즘을 사용하면 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)