C语言四道例题教会你，“双指针法”之对撞指针

目录

一、什么是双指针法

对撞指针

二、引例 – 数组逆置

方法一 类冒泡排序

方法二 临时数组

方法三 数组双下标法

三、查找数字

方法一 暴力查找

方法二 二分查找

四、将奇数移到偶数之前

五、杨氏矩阵

六、 小结

众所周知，数组的实质就是指针。为了体现该方法的普适性，表明该方法并不局限于指针，数组中也可以灵活运用。在本篇文章中所有的题目均以数组双下标的形式呈现。

一、什么是双指针法

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。在这里，我们聊一聊其中的对撞指针，快慢指针先按下不表，再往的文章中了解。

对撞指针

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

为了便于理解。不妨，我们来看一个动画。

二、引例 – 数组逆置

为了更好地说明这个问题，我们以一道牛客网的题目作引例。题目链接贴在这里
数组逆置__牛客网编写程序，按照指定长度生成动态数组，用随机数对数组元素进行赋https://www.nowcoder.com/questionTerminal/3d6a865e963641a0ad161e7cdb949e0f?

题干如下：

前言：

这道题目不难，但给了我们一个解题的新思路，利用数组的下标改变来解题。

最初，拿到这道题时。我脑海中第一个浮现出的是利用类似于冒泡排序的算法，将数组从头至尾历遍，并逆置出来。

方法一 类冒泡排序

int main(){int arr[]={6, 3, 7, 8, 2};int len=sizeof(arr)/sizeof(int);for(int i=0;i<len-1;i++){for(int j=0;j<len-1-i;j++){int tmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}}for(int i=0;i<len;i++){printf("%d ",arr[i]);}return 0;}

可是这样做的复杂度未免太高，有o(N^2)之多，有什么更好办法能让运行速度慢下来呢？

经验告诉我们，我们只有把上层的土刨开，我们才可以找到地底下的宝藏。由此可以得知，似乎我们可以为了保留数据，重新保留一份一模一样的数组。然后倒着装进原来的数组里。

方法二 临时数组

int main(){int arr[]={6, 3, 7, 8, 2};int len=sizeof(arr)/sizeof(int);int tmp[len];for(int i=0;i<len;i++)tmp[i]=arr[i];for(int i=0,j=len-1;i<len;i++,j--)arr[i]=tmp[j];for(int i=0;i<len;i++){printf("%d ",arr[i]);}}

但是，这样我们创造新的数组之后，如果数据量特别大，计算机不得不开辟出一块巨大的空间给临时数组，这样对计算机的空间又造成巨大的负担。那么如何不创造临时数组的情况下，提高运行速度呢？

其实我们可以巧妙地利用”双指针法”，将数组的运行效率大大提高。

基本思路：

定义一个最左端的下标left，和最右端的下标right，将两端的数组元素互。之后，left、right下标，同时自增和自减，

(left++,right–)，这样，随着不断地交换的同时，下标不断地向中间靠拢。直到left下标和right下标同时指向同一个元素，或者相邻元素时停止。这样，就完成了数组逆置。在运行速度上大大提高，也没有创建新的数组，造成空间压栈问题。

方法三 双指针法

int main(){int arr[]={6, 3, 7, 8, 2};int len=sizeof(arr)/sizeof(int);int left=0;int right=len-1;while(left<=right){int tmp=arr[left];arr[left]=arr[right];arr[right]=tmp;left++;right--;}int i=0;for(i=0;i<len;i++){printf("%d ",arr[i]);}return 0;}

三、查找数字

为了更好地说明这个问题以下是题目链接

二分查找- 力扣（LeetCode）给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。示例 1:输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4示例2:输入: nums = [-1,0,3,5,9,12], target = 2输出: -1解释: 2 不存在 nums 中因此返回 -1提示：你可以假设 nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。https://leetcode.cn/classic/problems/binary-search/description/题干如下：

前言：

当我们看到题目的时候，第一直觉肯定是暴力历遍。当然，暴力历遍能够做出来。

方法一 暴力查找

/*** 暴力历遍* @parama nums 数组* @parama numsSize数组长度* @parama target被查找值*/int search(int* nums, int numsSize, int target) {int i=0;for(i=0;i<numsSize;i++){if(target==nums[i])return i;}return -1;}

可是数据太多时又不太实用，有什么方法呢？其实，查找算法中存在一个专门用于此类查找的算法——二分查找算法，又叫折半查找。

基本思路：

在数组中元素都是有序排列的，令left = 0、right = numsSize-1，不妨我们选取一个中间量mid，mid = left + right，将被查找值 target 与 mid对比，如果假使 target nums[mid]，那么目标值就在数组右边，即，left = mid + 1。

方法二 二分查找

/*** 二分查找* @parama nums 数组* @parama numsSize数组长度* @parama target被查找值*/int search(int* nums, int numsSize, int target) {int left = 0;int right = numsSize -1;int mid=0;while(leftnums[mid]) left=mid+1;else if(target<nums[mid])right=mid-1;elsereturn mid;}return -1;}

以下是图像展示二分法和暴力查找之间的比较，速度快慢高下立判。

四、将奇数移到偶数之前

以下是《剑指offer》的一道OJ题作为示例

将奇数移到偶数之前- 力扣（LeetCode）. – 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/description/题干如下：

前言：

面对这道题第一直觉就是将数组拆分成奇数和偶数两个数组之后再合并，可是这样未免太过麻烦，况且我们都不知道数组中奇偶数分别为多少，也不知道创建一个多大的数组来存放各个数。历遍数组之后获取到数组大小后再创建数组未免太过麻烦，而且临时数组的创建会浪费大量的空间。因此，不得已的情况下我们不会创建临时数组。那么，我们试试用“双指针法”吧。

基本思路：

我们定义 ，最左端的下标 left = 0，最右端下标 right = len – 1。

当arr[left]为奇数时，left++，直到一直找到偶数，或者与right重合。同理，当arr[right]是偶数时，一直right–，直到找到奇数，或者与left重合。找到之后将两数互换，再继续left++，right–往下，直到 left 与 right 相遇之后停止。

/** * 将奇数移到偶数之前 * @parama actions 数组 * @parama actionsSize 数组大小 * @parama returnSize 返回的数组大小 */int* trainingPlan(int* actions, int actionsSize, int* returnSize) {int left=0;int right=actionsSize-1;while(left<right){while((left<right)&&(actions[left]%2!=0))left++;while((left<right)&&(actions[right]%2==0))right--;int tmp=actions[left];actions[left]=actions[right];actions[right]=tmp;}*returnSize=actionsSize;return actions;}

五、杨氏矩阵

通常意义上“对撞指针法”位于头尾向中间移动，但在二维数组的适当使用也可以起到出奇制胜的效果。接下来，我们以《剑指offer》的一道OJ题为例。

搜索二维矩阵 (Search a 2D Matrix) – 力扣 (LeetCode)https://leetcode.cn/problems/search-a-2d-matrix-ii/description/题干如下：

基本思路：

本题典型的杨氏矩阵问题

在m*n的数组arr中（杨氏矩阵），第m行的第1列数字和第n列的第1行数字是比较又特点的，不管在纵向还是在横向都是严格递增的。

我们可以以这样一个性质去设计解题思路。

从第m行的第1列开始。

不妨设 i 表示列，col表示行。

1.只要target(目标值)>arr[col]，那么就执行操作col++；

2.如果target(目标值)

3.如果target(目标值)=arr[i][col]，直接返回true。

要执行上述三个选择结构就需要用到循环结构，不难想到循环结构的终止条件如下：

①i>=0，即当执行到第1行第1列的时候（因为第1行的下标等于0，所以包含i=0），当执行到arr[0][0]的时候终止（到本二维数组中最小的数的时候）,也就意味着目标值比本二维数组最小值还要小；

②col

/*** 杨氏矩阵* @parama matrix 数组* @parama matrixSize 二维数组的元素个数，也就是杨氏矩阵的高；* @parama matrixColsize 一维数组的长度，也就是杨氏矩阵的宽* @parama target 目标值 */bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) { int col=0; int i=matrixColSize[0]-1;while((col=0)){if(target>matrix[col][i])col++;else if(target<matrix[col][i])i--;elsereturn true;}return false;}

六、 小结

那么我们什么时候用对撞指针呢？对撞指针的使用多见于需要历遍整个数组的题目当中。并且完成有规律的重复操作。往往当满足以上条件时，使用对撞指针能偶达到意料之外的效果。