跳至主要內容

 

labuladong约 12021 字大约 40 分钟数据结构数组双指针核心框架

Info

算法可视化编辑器上线,点击体验open in new window

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
167. Two Sum II - Input Array Is Sortedopen in new window167. 两数之和 II - 输入有序数组open in new window🟠
26. Remove Duplicates from Sorted Arrayopen in new window26. 删除有序数组中的重复项open in new window🟢
27. Remove Elementopen in new window27. 移除元素open in new window🟢
283. Move Zeroesopen in new window283. 移动零open in new window🟢
344. Reverse Stringopen in new window344. 反转字符串open in new window🟢
5. Longest Palindromic Substringopen in new window5. 最长回文子串open in new window🟠
83. Remove Duplicates from Sorted Listopen in new window83. 删除排序链表中的重复元素open in new window🟢
-剑指 Offer 57. 和为s的两个数字open in new window🟢
-剑指 Offer II 006. 排序数组中两个数字之和open in new window🟢

Tip

本文有视频版:数组双指针技巧汇总open in new window。建议关注我的 B 站账号,我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

在处理数组和链表相关问题时,双指针技巧是经常用到的,双指针技巧主要分为两类:左右指针快慢指针

所谓左右指针,就是两个指针相向而行或者相背而行;而所谓快慢指针,就是两个指针同向而行,一快一慢。

对于单链表来说,大部分技巧都属于快慢指针,前文 单链表的六大解题套路 都涵盖了,比如链表环判断,倒数第 K 个链表节点等问题,它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。

在数组中并没有真正意义上的指针,但我们可以把索引当做数组中的指针,这样也可以在数组中施展双指针技巧,本文主要讲数组相关的双指针算法

一、快慢指针技巧

数组问题中比较常见的快慢指针技巧,是让你原地修改数组

比如说看下力扣第 26 题「删除有序数组中的重复项open in new window」,让你在有序数组去重:

26. 删除有序数组中的重复项 | 力扣 open in new window | LeetCode open in new window |

给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被 通过

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 升序 排列

函数签名如下:

java 🟢
int removeDuplicates(int[] nums);

简单解释一下什么是原地修改:

如果不是原地修改的话,我们直接 new 一个 int[] 数组,把去重之后的元素放进这个新数组中,然后返回这个新数组即可。

但是现在题目让你原地删除,不允许 new 新数组,只能在原数组上操作,然后返回一个长度,这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。

由于数组已经排序,所以重复的元素一定连在一起,找出它们并不难。但如果毎找到一个重复元素就立即原地删除它,由于数组中删除元素涉及数据搬移,整个时间复杂度是会达到 O(N^2)

高效解决这道题就要用到快慢指针技巧:

我们让慢指针 slow 走在后面,快指针 fast 走在前面探路,找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。

这样,就保证了 nums[0..slow] 都是无重复的元素,当 fast 指针遍历完整个数组 nums 后,nums[0..slow] 就是整个数组去重之后的结果。

看代码:

java 🟢
int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
}

算法执行的过程如下 GIF 图:

再简单扩展一下,看看力扣第 83 题「删除排序链表中的重复元素open in new window」,如果给你一个有序的单链表,如何去重呢?

其实和数组去重是一模一样的,唯一的区别是把数组赋值操作变成操作指针而已,你对照着之前的代码来看:

java 🟢
ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    while (fast != null) {
        if (fast.val != slow.val) {
            // nums[slow] = nums[fast];
            slow.next = fast;
            // slow++;
            slow = slow.next;
        }
        // fast++
        fast = fast.next;
    }
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
}

算法执行的过程请看下面这个 GIF:

这里可能有读者会问,链表中那些重复的元素并没有被删掉,就让这些节点在链表上挂着,合适吗?

这就要探讨不同语言的特性了,像 Java/Python 这类带有垃圾回收的语言,可以帮我们自动找到并回收这些「悬空」的链表节点的内存,而像 C++ 这类语言没有自动垃圾回收的机制,确实需要我们编写代码时手动释放掉这些节点的内存。

不过话说回来,就算法思维的培养来说,我们只需要知道这种快慢指针技巧即可。

除了让你在有序数组/链表中去重,题目还可能让你对数组中的某些元素进行「原地删除」

比如力扣第 27 题「移除元素open in new window」,看下题目:

27. 移除元素 | 力扣 open in new window | LeetCode open in new window |

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

函数签名如下:

java 🟢
int removeElement(int[] nums, int val);

题目要求我们把 nums 中所有值为 val 的元素原地删除,依然需要使用快慢指针技巧:

如果 fast 遇到值为 val 的元素,则直接跳过,否则就赋值给 slow 指针,并让 slow 前进一步。

这和前面说到的数组去重问题解法思路是完全一样的,就不画 GIF 了,直接看代码:

java 🟢
int removeElement(int[] nums, int val) {
    int fast = 0, slow = 0;
    while (fast < nums.length) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

注意这里和有序数组去重的解法有一个细节差异,我们这里是先给 nums[slow] 赋值然后再给 slow++,这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的,最后的结果数组长度就是 slow

实现了这个 removeElement 函数,接下来看看力扣第 283 题「移动零open in new window」:

给你输入一个数组 nums,请你原地修改,将数组中的所有值为 0 的元素移到数组末尾,函数签名如下:

java 🟢
void moveZeroes(int[] nums);

比如说给你输入 nums = [0,1,4,0,2],你的算法没有返回值,但是会把 nums 数组原地修改成 [1,4,2,0,0]

结合之前说到的几个题目,你是否有已经有了答案呢?

题目让我们将所有 0 移到最后,其实就相当于移除 nums 中的所有 0,然后再把后面的元素都赋值为 0 即可。

所以我们可以复用上一题的 removeElement 函数:

java 🟢
void moveZeroes(int[] nums) {
    // 去除 nums 中的所有 0,返回不含 0 的数组长度
    int p = removeElement(nums, 0);
    // 将 nums[p..] 的元素赋值为 0
    for (; p < nums.length; p++) {
        nums[p] = 0;
    }
}

// 见上文代码实现
int removeElement(int[] nums, int val);

到这里,原地修改数组的这些题目就已经差不多了。数组中另一大类快慢指针的题目就是「滑动窗口算法」。

我在另一篇文章 滑动窗口算法核心框架详解 给出了滑动窗口的代码框架:

cpp 🟢
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    while (right < s.size()) {
        char c = s[right];
        // 右移(增大)窗口
        right++;
        // 进行窗口内数据的一系列更新

        while (window needs shrink) {
            char d = s[left];
            // 左移(缩小)窗口
            left++;
            // 进行窗口内数据的一系列更新
        }
    }
}

具体的题目本文就不重复了,这里只强调滑动窗口算法的快慢指针特性:

left 指针在后,right 指针在前,两个指针中间的部分就是「窗口」,算法通过扩大和缩小「窗口」来解决某些问题。

二、左右指针的常用算法

1、二分查找

我在另一篇文章 二分查找框架详解 中有详细探讨二分搜索代码的细节问题,这里只写最简单的二分算法,旨在突出它的双指针特性:

java 🟢
int binarySearch(int[] nums, int target) {
    // 一左一右两个指针相向而行
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

2、两数之和

看下力扣第 167 题「两数之和 IIopen in new window」:

167. 两数之和 II - 输入有序数组 | 力扣 open in new window | LeetCode open in new window |

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]numbers[index2] ,则 1 <= index1 < index2 <= numbers.length

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 index2

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

 

示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers非递减顺序 排列
  • -1000 <= target <= 1000
  • 仅存在一个有效答案

只要数组有序,就应该想到双指针技巧。这道题的解法有点类似二分查找,通过调节 leftright 就可以调整 sum 的大小:

java 🟢
int[] twoSum(int[] nums, int target) {
    // 一左一右两个指针相向而行
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 题目要求的索引是从 1 开始的
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return new int[]{-1, -1};
}

我在另一篇文章 一个函数秒杀所有 nSum 问题 中也运用类似的左右指针技巧给出了 nSum 问题的一种通用思路,这里就不做赘述了。

3、反转数组

一般编程语言都会提供 reverse 函数,其实这个函数的原理非常简单,力扣第 344 题「反转字符串open in new window」就是类似的需求,让你反转一个 char[] 类型的字符数组,我们直接看代码吧:

java 🟢
void reverseString(char[] s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length - 1;
    while (left < right) {
        // 交换 s[left] 和 s[right]
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

4、回文串判断

首先明确一下,回文串就是正着读和反着读都一样的字符串。

比如说字符串 abaabba 都是回文串,因为它们对称,反过来还是和本身一样;反之,字符串 abac 就不是回文串。

现在你应该能感觉到回文串问题和左右指针肯定有密切的联系,比如让你判断一个字符串是不是回文串,你可以写出下面这段代码:

java 🟢
boolean isPalindrome(String s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

那接下来我提升一点难度,给你一个字符串,让你用双指针技巧从中找出最长的回文串,你会做吗?

这就是力扣第 5 题「最长回文子串open in new window」:

5. 最长回文子串 | 力扣 open in new window | LeetCode open in new window |

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

函数签名如下:

java 🟢
String longestPalindrome(String s);

找回文串的难点在于,回文串的的长度可能是奇数也可能是偶数,解决该问题的核心是从中心向两端扩散的双指针技巧

如果回文串的长度为奇数,则它有一个中心字符;如果回文串的长度为偶数,则可以认为它有两个中心字符。所以我们可以先实现这样一个函数:

java 🟢
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
    // 防止索引越界
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
        // 双指针,向两边展开
        l--; r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substring(l + 1, r);
}

这样,如果输入相同的 lr,就相当于寻找长度为奇数的回文串,如果输入相邻的 lr,则相当于寻找长度为偶数的回文串。

那么回到最长回文串的问题,解法的大致思路就是:

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

翻译成代码,就可以解决最长回文子串这个问题:

java 🟢
String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        // 以 s[i] 为中心的最长回文子串
        String s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        String s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}

你应该能发现最长回文子串使用的左右指针和之前题目的左右指针有一些不同:之前的左右指针都是从两端向中间相向而行,而回文子串问题则是让左右指针从中心向两端扩展。不过这种情况也就回文串这类问题会遇到,所以我也把它归为左右指针了。

到这里,数组相关的双指针技巧就全部讲完了,这些技巧的更多扩展延伸见 更多数组双指针经典高频题


引用本文的文章


引用本文的题目

安装 我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路:

LeetCode力扣
1. Two Sumopen in new window1. 两数之和open in new window
125. Valid Palindromeopen in new window125. 验证回文串open in new window
131. Palindrome Partitioningopen in new window131. 分割回文串open in new window
267. Palindrome Permutation IIopen in new window🔒267. 回文排列 IIopen in new window🔒
281. Zigzag Iteratoropen in new window🔒281. 锯齿迭代器open in new window🔒
42. Trapping Rain Wateropen in new window42. 接雨水open in new window
658. Find K Closest Elementsopen in new window658. 找到 K 个最接近的元素open in new window
80. Remove Duplicates from Sorted Array IIopen in new window80. 删除有序数组中的重复项 IIopen in new window
82. Remove Duplicates from Sorted List IIopen in new window82. 删除排序链表中的重复元素 IIopen in new window
9. Palindrome Numberopen in new window9. 回文数open in new window
-剑指 Offer 21. 调整数组顺序使奇数位于偶数前面open in new window
-剑指 Offer 57. 和为s的两个数字open in new window
-剑指 Offer II 018. 有效的回文open in new window

《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶