跳至主要內容

双指针技巧的详解

linwu大约 2 分钟

双指针技巧的详解

双指针技巧是一个经常在各类算法题目中出现的解决问题的策略。这种策略主要用于解决需要在一个线性结构(例如数组或链表)中查找、修改或比较元素的问题。双指针技巧通常用于优化暴力求解或其他高复杂度解法,减少时间和空间复杂度。

双指针的主要应用

  1. 对撞指针:两个指针从不同的方向向中间移动,通常用于有序数组或链表的问题,例如「两数之和」、「反转字符串」。

  2. 快慢指针:两个指针以不同的速度移动,通常用于链表问题,例如「检测环」、「找到中点」。

  3. 滑动窗口:两个指针维护一个窗口,通常用于数组或链表的连续或固定大小子序列问题,例如「无重复字符的最长子串」、「最小覆盖子串」。

算法框架

function doublePointer(arr) {
    let left = 0, right = 0;
    let ans = ...;  // 根据具体问题确定初始值

    while (right < arr.length) {
        // 根据具体问题更新答案
        // ...

        // 移动右指针
        right++;

        while (/*根据具体问题确定左指针何时移动的条件*/) {
            // 移动左指针
            left++;
        }
    }

    return ans;
}

注意,这个框架可能需要根据具体问题进行一些微调。

双指针技巧的应用举例

  1. 对撞指针:「反转字符串」

    function reverseString(s) {
        let left = 0, right = s.length - 1;
        while (left < right) {
            let temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }
    
  2. 快慢指针:「寻找链表中点」

    function middleNode(head) {
        let slow = head, fast = head;
        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
  3. 滑动窗口:「无重复字符的最长子串」

    function lengthOfLongestSubstring(s) {
        let map = {};
        let longest = 0;
        let start = 0;
        for (let i = 0; i < s.length; i++) {
            let char = s[i];
            if (map[char] !== undefined) {
                start = Math.max(start, map[char] + 1);
            }
            map[char] = i;
            longest = Math.max(longest, i - start + 1);
        }
        return longest;
    }
    

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群