”工欲善其事,必先利其器。“—孔子《论语.录灵公》
首页 > 编程 > 二指针算法解释

二指针算法解释

发布于2024-11-08
浏览:408

Two pointers algorithm explained

我想解释一个简单有效的技巧,你可以在面试中处理数组、字符串、链表等时使用它。这也将提高你对这些数据的基础知识结构。

让我们从理论开始。该算法有两个常见用例:

  • 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 

让我们切换到指针具有不同速度的方法。这是一个常见的问题,你可以在面试中遇到。您需要找到给定链接列表的中间位置。
蛮力方法并不像前面的例子那么糟糕,但面试官期望有更好的方法。
使用两个指针算法,您将以 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)


版本声明 本文转载于:https://dev.to/okaz/two-pointers-algorithm-explained-3k0e?1如有侵犯,请联系[email protected]删除
最新教程 更多>

免责声明: 提供的所有资源部分来自互联网,如果有侵犯您的版权或其他权益,请说明详细缘由并提供版权或权益证明然后发到邮箱:[email protected] 我们会第一时间内为您处理。

Copyright© 2022 湘ICP备2022001581号-3