详细解析如何用“双指针“解题（面试必备，小白一看就会系类）

一、前言

大家在平时的训练和交流中肯定多少都会听过或者见过用"双指针"去快速的解题，那么大家有没有想过，为什么要用"双指针"呢？这里的"双指针"和我们平时了解的指针一样吗？

其实，这里的“双指针”，并不是我们平直所了解的指针（指向地址空间的指针），而是我们想象出来的逻辑指挥棒-------简称“双指针”，这样不仅方便我们的画图，同时能让我们在解题时的时间复杂度和空间复杂度大大降低。

下面我将通过个几个简单的面试题，来带大家慢慢体会“双指针的魅力”。

二、面试题

🍎删除有序数组中的重复项

🔑本题的来源力扣：删除有序数组中的重复项

🔑题目的大概意思：

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

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

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

返回 k 。

🔑题目输入：nums[0,0,1,1,1,2,2,3,3,4]

🔑题目输出：5，nums[0,1,2,3,4]

💦题目解析

▶ 通常大家见到这种类型的题目，首先肯定会想到的是从前往后重复遍历整个数组，遇到重复的数据删除，让后面的数据往前挪，此时会发现时间复杂度和空间复杂度比较高。

▶ 如果我们定义两个指挥棒 start 和 end 来指挥数据的变动，此时只需要遍历一次数组即可。当nums[start]==nums[end] 时start就向前挪动，否则 end 向前挪动，将start位置的值赋予个给end位置，这样依次交替转换，直到start遍历整个数组，返回end小标的数组即可。

💦图解分析

💦解题代码
int removeDuplicates(int* nums, int numsSize)
{// 自己写// 双指针// 这里的双指针，是一个指定向的符号，帮助我们更好的处理数组int src = 0;int dst = 0;while(src<numsSize){if(nums[src]==nums[dst]){src++;}else{dst++;nums[dst]=nums[src];src++;}}return dst+1;
}

🍐移除元素

🔑本题的来源力扣：移除元素

🔑题目的大概意思：

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

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

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

🔑题目输入：nums[0,1,2,2,3,0,4,2] val = 2

🔑题目输出：5，nums[0,1,4,0,3]

💦题目解析

▶ 这道题和上一道题目很像，同样定义两个指挥棒 start 和 end 来指挥数据的变动，当start ==val 时，start向前挪动，否则 nums[start]=nums[end] , end 和 start同时向前挪动。

💦图解分析

💦解题代码
nt removeElement(int* nums, int numsSize, int val)
{// 自己写// 使用双指针// 定义两个指向符int scr=0;int dst=0;while(scr<numsSize){if(nums[scr]!=val){nums[dst] = nums[scr];dst++;scr++;}else{scr++;}}return dst;
}

🍑合并两个有序数组

🔑本题的来源力扣：合并两个有序数组

🔑题目的大概意思：

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

🔑题目输入：nums1[1,2,3,0,0,0], m=3 nums2[2,4,6] n=3

🔑题目输出：nums[1,2,2,3,4,6]

💦题目解析

▶ 根据题目的题意，我们可以设置三个指挥棒 end1表示nums1有效数据的尾下标，end2表示nums2有效数据的尾下标，end 表示整个nums1数组的尾下标，我们通过比较nums1和nums2有效数据的大小，取大（从后往前比），将大据的数据，重新尾插在nums1上即可。

💦图解分析

🔑 nums2[end2]>nums[end1]

🔑 nums2[end2]>nums[end1]

🔑 nums2[end2]>nums[end1]

🔑 nums2[end2]<nums[end1]

🔑 nums2[end2]=nums[end1]

💦解题代码
oid merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// 自己写// 双指针int end1 = m-1;int end2 = n-1;int end = m+n-1;while(end1>=0&&end2>=0){if(nums1[end1]>nums2[end2]){nums1[end--] = nums1[end1--];}else{nums1[end--] = nums2[end2--];}}while(end2>=0){nums1[end--] = nums2[end2--];}return nums1;
}