双指针学习笔记

139天前 · 代码 · 396次阅读

在数组问题中,有一类非常常见的技巧——双指针。顾名思义是用两个指针(变量)来记录一些关键信息。那么首先我们需要了解一下,那些关键信息是什么?

本文为算法学习的一篇笔记,观看本文可能需要一些前置知识

循环不变量

其实那些关键信息绝大部分是循环不变量。「循环不变量」是指我们在编写代码的过程中,要一直循序不变的性质,这样的性质是根据要解决的问题,由我们自己定义的。他还需要保证在解题过程中的三个阶段内的性质不变,这样才能作为我们解题的基础。这三个阶段分别是

  1. 初始化
  2. 循环遍历
  3. 结束

举个例子: 27. 移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let len = nums.length;
    let i = 0;

    for(let j = 0; j < len; j ++)
        if(nums[j] != val)
            nums[i++] = nums[j];

    return i;
};

这里,我定义区间$[0,i]$为我的移除元素后的数组边界,那么此时他就是我的第一个指针(即循环不变量)。而j则是我正常遍历的第二个指针。

那么初始化时,我的i作为移除元素后的数组边界,此时应该是长度为0的(因为还没有开始解题)

在使用第二个指针遍历数组期间,我也根据区间$[0,i]$的性质与逻辑去编写相应的代码。这里就是当遍历到的元素不为需要移除的元素的时候,就将当前元素赋值给指针i指向的位置,时刻保持着他的性质都是「移除元素后的数组边界」

在结尾时,因为我在遍历期间始终保持着指针i的性质,那我很轻易就可以知道,我的需要的答案就是此时的i了。

最后稍微总结一下。循环不变量本身的意义就在于你怎么去定义它的,你想让他记录什么,那么在初始化的时候就根据相应的逻辑进行初始化,在遍历的时候也根据相应的逻辑进行操作。最后得到的,就是你想要的东西。

留个小问题:283. 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let len = nums.length,
        left = 0,
        right = 0;

    while(right < len) {
        if(nums[right]) {
            let temp = nums[left];
            nums[left++] = nums[right];
            nums[right] = temp;
        }
        right++;
    }
};

这里我的left指针维护的是个什么呢?

答案

实际上是数组非零部分的边界,也就是说$[0, left)$区间内的都是原数组中的非零部分,而$[left, len-1]$则是数组全部的0。

双指针

其实说完循环不变量,双指针的精髓也差不多介绍完了。其实双指针是非常灵活的一种技巧,每一题的双指针的含义,都是对题目进行充分理解后总结出的。但是也有些规律,例如上面的移动零和移除元素两道题,是通过某一指针去维护一个内容区间,而有一些又不是如此。我凭借我微乎其微的写题经验稍微总结了一下,大概有以下几种

  1. 区间维护(例题:283. 移动零 | 27. 移除元素 75. 颜色分类
  2. 类似于动态规划的双指针(例题:167. 两数之和 II - 输入有序数组 | 11. 盛最多水的容器
  3. 快慢指针(例题:19. 删除链表的倒数第 N 个结点 | 876. 链表的中间结点

第一种刚刚已经说过了,接下来再介绍一下第二种:类似DP的双指针。

11. 盛最多水的容器作为例题

/**
 * @param {number[]} h
 * @return {number}
 */
var maxArea = function(h) {
    let len = h.length,
        left = 0,
        right = len - 1,
        result = 0;
    
    while(left < right) {
        result = Math.min(h[left], h[right]) * (right - left) > result ? Math.min(h[left], h[right]) * (right - left) : result;
        if(h[left] > h[right]) right--;
        else left++;
    }

    return result;
};

这里的双指针的作用是作为边界从两侧同时遍历数组,动态地去查找最大容量。基本逻辑是这样子的:双指针leftright,分别从区间两侧逼近,每次计算当前两个指针所围成的容器大小与之前的最大值进行比较,比之前的最大值还大则保存。接下来就是较小的那一边移动直到两指针相交。最后的结果就是我们记录的最大值。

167. 两数之和 II - 输入有序数组也是类似的逻辑。

最后一种快慢指针,也是一种非常巧妙的技巧。两个指针根据含义,设置不同的移动步长。例如例题876. 链表的中间结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* p1 = head, *p2 = head->next;
        
        while(p2 != nullptr) {
            p2 = p2->next;
            p1 = p1->next;
            if(p2 == nullptr) return p1;
            p2 = p2->next;
        }
        
        return p1;
    }
};

要求寻找链表的中间节点,那么此时的我的快指针的步长就应该是我慢指针步长的两倍,这样子当我的快指针到链尾时,我的慢指针就刚刚好到了中间节点。

小结

双指针技巧对于吾等暴力算法受害者 是天大的福音,多加体会,咱也能把自己的$O(n^3)$代码优化到线性$O(n)$复杂度。但是要熟练掌握这种方法还不能纯靠悟,还需要多加练习,才能避免再出现三层for循环的黑暗代码

👍 5

算法 双指针

最后修改于128天前

评论

贴吧 狗头 原神 小黄脸
收起

贴吧

狗头

原神

小黄脸

  1. 君衍 114天前

    学到了

  2. 常瑞 125天前

    不错不错!

  3. ZigZagK 135天前

    双指针大法好

    1. 季悠然 134天前

      真的是太美妙了

  4. Rainiar 138天前

    最后一段到底是c++还是伪代码(
    血压上升了

    1. 季悠然 138天前

      是c++

目录

avatar

季悠然

寻找有趣的灵魂

127

文章数

1954

评论数

3

分类

好热啊

arknights!

猫是可爱的,狼是很帅的。就是说,孤独又可爱又帅。

107