二指针算法解释-js教程-PHP中文网

二指针算法解释

聖光之護

发布： 2024-10-07 22:09:00

转载

1116人浏览过

二指针算法解释

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

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

左/右该算法的中心概念是有两个整数变量，它们将从字符串或数组的两侧移动。通常，人们称之为左和右。左边将从 0 索引移动到长度 — 1，右边则相反。

Python精要参考 pdf版
这本书给出了一份关于python这门优美语言的精要的参考。作者通过一个完整而清晰的入门指引将你带入python的乐园，随后在语法、类型和对象、运算符与表达式、控制流函数与函数编程、类及面向对象编程、模块和包、输入输出、执行环境等多方面给出了详尽的讲解。如果你想加入 python的世界，David M beazley的这本书可不要错过哦。 (封面是最新英文版的,中文版貌似只译到第二版)

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]

登录后复制

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