双指针学习笔记

1018天前 · 代码 · 1707次阅读

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

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

循环不变量

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

  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;
    }
};

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

小结

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

👍 5

算法 双指针

最后修改于1007天前

评论

贴吧 狗头 原神 小黄脸
收起

贴吧

  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡

狗头

  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头

原神

  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神

小黄脸

  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  1. 尽快 828天前

    啦啦啦啦啦啦啦

  2. 君衍 993天前

    学到了 shuijiao

  3. 常瑞 1004天前

    不错不错!

  4. ZigZagK 1014天前

    双指针大法好 [doge]

    1. 季悠然 1013天前

      真的是太美妙了 [惊喜]

  5. Rainiar 1017天前

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

    1. 季悠然 1017天前

      是c++ huaji_han

目录

avatar

季悠然

寻找有趣的灵魂

140

文章数

2097

评论数

3

分类

好热啊

arknights!

你对世界所付出的善意,终究会开花结果。

会说话的肘子

1526