双指针技巧秒杀七道数组题目

labuladong 原创约 3656 字

167. 两数之和 II - 输入有序数组 https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted

26. 删除有序数组中的重复项 https://leetcode.cn/problems/remove-duplicates-from-sorted-array

27. 移除元素 https://leetcode.cn/problems/remove-element

283. 移动零 https://leetcode.cn/problems/move-zeroes

344. 反转字符串 https://leetcode.cn/problems/reverse-string

5. 最长回文子串 https://leetcode.cn/problems/longest-palindromic-substring

83. 删除排序链表中的重复元素 https://leetcode.cn/problems/remove-duplicates-from-sorted-list

剑指 Offer 57. 和为s的两个数字 https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof

剑指 Offer II 006. 排序数组中两个数字之和 https://leetcode.cn/problems/kLl5u1

本文讲解的例题

LeetCode	力扣	难度
167. Two Sum II - Input Array Is Sorted	167. 两数之和 II - 输入有序数组	🟠
26. Remove Duplicates from Sorted Array	26. 删除有序数组中的重复项	🟢
27. Remove Element	27. 移除元素	🟢
283. Move Zeroes	283. 移动零	🟢
344. Reverse String	344. 反转字符串	🟢
5. Longest Palindromic Substring	5. 最长回文子串	🟠
83. Remove Duplicates from Sorted List	83. 删除排序链表中的重复元素	🟢
-	剑指 Offer II 006. 排序数组中两个数字之和	🟢
-	剑指 Offer 57. 和为s的两个数字	🟢

前置知识

阅读本文前，你需要先学习：

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

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

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

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

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 。不需要考虑数组中超出新长度后面的元素。


             nums

已按 非严格递增 排列

题目来源：力扣 26. 删除有序数组中的重复项。

函数签名如下：

java 🟢

int removeDuplicates(int[] nums);

cpp 🤖

int removeDuplicates(vector<int>& nums);

python 🤖

def removeDuplicates(nums: List[int]) -> int:

go 🤖

func removeDuplicates(nums []int) int {}

javascript 🤖

var removeDuplicates = function(nums) {};

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

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

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

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

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

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

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

看代码：

java 🟢

class Solution {
    public 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;
}

cpp 🤖

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        int slow = 0, fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] != nums[slow]) {
                slow++;
                // 维护 nums[0..slow] 无重复
                nums[slow] = nums[fast];
            fast++;
        // 数组长度为索引 + 1
        return slow + 1;
};

python 🤖

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        slow = 0 
        fast = 1
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow += 1
                # 维护 nums[0..slow] 无重复
                nums[slow] = nums[fast]
            fast += 1
        # 数组长度为索引 + 1
        return slow + 1

go 🤖

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    slow,fast :=0,0
    for fast<len(nums) {
        if nums[fast] != nums[slow] {
            slow++
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast]
        fast++
    // 数组长度为索引 + 1
    return slow + 1
}

javascript 🤖

var removeDuplicates = function(nums) {
    if (nums.length == 0) {
        return 0;
    var 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;
};

你可以打开下面的可视化面板，多次点击 while (fast < nums.length) 这一行代码，即可看到两个指针维护 nums[0..slow] 无重复元素：

Algorithm visualize

算法可视化面板 Link copied!