双指针总结(必备8篇)

双指针总结 第1篇

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

两层for循环，一个for循环遍历数组元素 ，找到需要移除的元素；第二个for循环更新数组，让目标元素以后的数值都向前移动一位，覆盖目标移除的元素。

时间复杂度： O ( n 2 ) O(n^2) O(n2)

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 双指针法（快慢指针法） 在数组和链表的操作中非常常见，经常用于考察数组、链表、字符串

定义快慢两个指针，快指针指向当前将要处理的元素，慢指针指向下一个将要赋值的位置。在遇到目标值前，快慢指针相等，共同前移遍历；遇到目标值，快指针继续自增，慢指针停留，在之后将快指针指向的值赋给慢指针指向的值，实现覆盖目标值，整个数组前移。遍历完成后，慢指针最后停留的位置即是数组末尾的位置，即数组现在的长度。nums[0…slow] 就是不重复元素。 （图片来自代码随想录）

时间复杂度： O ( n ) O(n) O(n) 在最坏情况下（输入数组中没有元素等于val），左右指针各遍历了数组一次。需要遍历该序列至多两次

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为1时，我们需要把每一个元素都左移一位。题目中要求要原地移除，但元素的顺序可以改变。实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。这个优化在序列中val元素的数量较少时非常有效。

使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

如果左指针left 指向的元素等于val，此时将右指针right 指向的元素复制到左指针left 的位置，然后右指针right 左移一位。如果赋值过来的元素恰好也等于val，可以继续把右指针right 指向的元素的值赋值过来（左指针 left 指向的等于val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于val 为止。

当左指针 left 和右指针right 重合的时候，左右指针遍历完数组中所有的元素。此时数组前半段是有效部分，存储的是不等于 val 的元素；后半段（末尾部分）是无效部分，存储的是等于 val 的元素。

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。避免了需要保留的元素的重复赋值操作。

时间复杂度： O ( n ) O(n) O(n) 只需要遍历该序列至多一次。

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

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

时间复杂度： O ( n ) O(n) O(n)

或单独讨论数组长度为0的情况，指针从1取起

因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素nums[slow−2] 是否和当前待检查元素nums[fast] 相同。当且仅当nums[slow−2]=nums[fast] 时，当前待检查元素 nums[fast] 不应该被保留（因为此时必然有nums[slow−2]=nums[slow−1]=nums[fast]）。最后，slow 即为处理好的数组的长度。

特别地，数组的前两个数必然可以被保留，因此对于长度不超过 2 的数组，我们无需进行任何处理，对于长度超过 2 的数组，我们直接将双指针的初始值设为 2 即可。

时间复杂度： O ( n ) O(n) O(n)

由于是保留 k 个相同数字，对于前 k 个数字，我们可以直接保留

对于后面的任意数字，能够保留的前提是：与当前写入的位置前面的第 k 个元素进行比较，不相同则保留

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 1.必须在原数组上操作，不能拷贝额外的数组。 2.尽量减少操作次数。

相当于对整个数组用双指针法移除元素0，然后slow之后都是移除元素0的冗余元素，最后把这些元素都赋值为0就可以了。

双指针总结 第2篇

双指针技巧可细分分为两类，一类是快慢指针，一类是左右指针。

前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环、反转链表、找链表的中间节点、删除链表的倒数第 N 个结点；也用来解决数组中的问题，如移动/移除元素、删除有序数组中的重复项。

后者主要解决数组（或者字符串）中的问题，比如二分查找，滑动窗口。

双指针总结 第3篇

  通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用两个指针进行迭代。 双指针的典型场景 (1)从两端向中间迭代数组。 (2)一个指针从头部开始，而另一个指针从尾部开始。

c

c++

C

解析： 函数 qsort是C语言标准库中用于对数组进行快速排序的函数。它的函数原型如下：

qsort函数的第一个参数是需要排序的数组的指针base，第二个参数是数组的元素个数nitems，第三个参数是每个元素的大小size（以字节为单位），第四个参数是一个指向比较函数的指针compar。

比较函数compar接受两个指向待比较元素的指针，并返回一个整数值，表示它们的大小关系。如果第一个元素小于第二个元素，则返回一个负数；如果它们相等，则返回0；如果第一个元素大于第二个元素，则返回一个正数。这个函数的原型如下：

C++

c

解释: 函数 twoSum 接受四个参数： numbers：一个指向整数数组开头的指针 numbersSize：表示 numbers 数组的大小的整数 target：目标整数 returnSize：一个指向整数的指针，用于返回结果数组的大小

c++

c

c++

双指针总结 第4篇

只用双指针法时间复杂度为O(n^2)，但比xxx的O(n^2)效率高得多，xxx在使用两层for循环的时候，能做的剪枝操作很有限。

在双指针法：一样的道理，能解决四数之和中，讲到了四数之和，其实思路是一样的，「在三数之和的基础上再套一层for循环，依然是使用双指针法。」

对于三数之和使用双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

同样的道理，五数之和，n数之和都是在这个基础上累加。

总结本文中一共介绍了leetcode上九道使用双指针解决问题的经典题目，除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为O(n)。

建议大家可以把文中涉及到的题目在好好做一做，琢磨琢磨，基本对双指针法就不在话下了。

在留言区留下你的思路吧！

-------end-------

我将算法学习相关的资料已经整理到了Github ：，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图看一看一定会有所收获，如果给你有帮助给一个star支持一下吧！

另外因为公众号改版，时间线被打乱，一些精彩文章大家可能错过了。如果感觉这里的文章对你有帮助，赶紧给「代码随想录」加一个星标吧，方便第一时间阅读文章。

双指针总结 第5篇

有一类问题只是名字上叫「滑动窗口」，但解决这一类问题需要用到常见的数据结构。这一节给出的问题可以当做例题进行学习，一些比较复杂的问题是基于这些问题衍生出来的。

Naive implementation O(n^2)

方法二 Priority_queue

方法三, 单调队列, O(n)

保持单调递增或者递减的队形, 如果有问题

写法一

写法二，相对常规一些:

Brute Force 忽略 O(n^2)

方法二 Prefix Max O(n) 空间复杂度也是 O(n)

注意到l[i], 单调增的 r[i]单调减

所以对于每个i, 左侧的l[i]是单调增的, 右侧单调减法，和指针移动方向一致，考虑使用双指针

这个题跟上面有点像, 区别在于只能选择一个矩形来放水

矩形的面积有两个因素，一个是r-l, 另一个是两侧高度，从两边出发，trade length for height

双指针总结 第6篇

「滑动窗口」是一类通过使用两个变量在数组上同向交替移动解决问题的算法。这一类问题的思考路径通常是：先思考暴力解法，分析暴力解法的缺点（一般而言暴力解法的缺点是重复计算），然后 结合问题的特点，使用「双指针」技巧对暴力解法进行剪枝。因此，思考算法设计的合理性是更关键的，这一点适用于所有算法问题。

S,T 找出S中最小的滑动窗口,. contains T中所有元素（可重复）

朴素版本

假设需要压缩空间复杂度，那么

无重复字符的最长字串

找到最短的subarray，使得其和>=target

也可以用二分, 复杂度 O(n\log{n})

细节是sums数组比nums多一位,所以()在nums数组中对应的位置应该左移一位

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

复杂度O(26*n)

可以进一步优化，寻找count从0变成非0或者非0变成0的临界点，统计不均衡的字母数

一个数组中最多有多少个1?

跟上一题的区别是可以反转一个1。

考虑每个0的地方，考察pre[i], suf[i]两个预处理的数组，累加前后可能的最长连续1，其实已经用到了动态规划思想。

另一种DP适合流式数据, 令dp[i][0]表示0次操作后i结尾的数组最长的1是多少

d p[i][0]=\left\{\begin{array}{c} d p[i-1][0]+1, \text { nums }[i]=1 \\ 0, \text { nums }[i]=0 \end{array}\right.

并且:

d p[i][1]=\left\{\begin{array}{l} d p[i-1][1]+1, n u m s[i]=1 \\ d p[i-1][0]+1, n u m s[i]=0 \end{array}\right.

由此得到的代码是:

允许k次反转机会，求最长的1

这题有三种解法。

首先还是考虑dp[i][k], 时间复杂度O(kn), 处理corner case时候TLE

双指针的做法就是保持左右指针i,j,统计cnt不超过k

从前缀和出发，可以得到二分搜索O(nlgn）的解法

基于前缀和也可以优化，因为前缀和统计cumluative 0的个数，这个个数是只增不减的。

s,p两个字符串等长，maxCost变换成本以内的最大共同字串。

可以等价于diff数组小于等于maxCost的最大字串

二分法的解法如下:

Given a binary array nums, you should delete one element from it.

C++ DP 前缀后缀

方法二是考虑i为结尾，之前全1或者有一个0的子数组。

方法三，sliding window, 滑动窗口

Maintain一个窗口, . 窗口之和>=r-l

可以把0换成1， 问最多连续多少个0或者1

可以分两次考虑 分别考虑连续统计0或者1 转换成1004题

双指针总结 第7篇

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

将数组中每个数平方，再排序 时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)

数组是有序的， 负数平方后可能成为最大数。 那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

可以考虑双指针法，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i]; 。

（图片来自代码随想录）

时间复杂度： O ( n ) O(n) O(n)

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O ( 1 ) O(1) O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1： 输入：[“h”,“e”,“l”,“l”,“o”] 输出：[“o”,“l”,“l”,“e”,“h”]

示例 2： 输入：[“H”,“a”,“n”,“n”,“a”,“h”] 输出：[“h”,“a”,“n”,“n”,“a”,“H”]

分别指向字符串首尾，交换。

交换时可以用位运算写法：异或运算

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

和15.三数之和是一个思路，都是使用双指针法。一样的道理，五数之和、六数之和等等都采用这种解法。

四数之和的双指针解法是两层for循环nums[j] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[j] + nums[i] + nums[left] + nums[right] == target的情况。四数之和的双指针解法就是将原本暴力 O ( n 4 ) O(n^4) O(n4)的解法，降为 O ( n 3 ) O(n^3) O(n3)的解法

时间复杂度： O ( n 3 ) O(n^3) O(n3)

动规做法见 动态规划——子序列问题

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1： 输入：“abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”

示例 2： 输入：“aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示： 输入的字符串长度不会超过 1000 。

首先确定回文串的中心位置，就是找中心然后向两边扩散看是不是对称的就可以了，遇到不是回文的时候结束。

在遍历中心点的时候，要注意中心点有两种情况:一个元素可以作为中心点，两个元素也可以作为中心点。 这两种情况可以放在一起计算，也可分别计算，思路更清晰。

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

双指针中心扩散法

双指针总结 第8篇

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3

Output: 16

Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.

The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

数组中最左或者最右的元素，什么时候可以凑齐x, 并且数目最小?