C++实现双指针算法_c++ 双指针排序

双指针算法指的是，从数组的两侧开辟指针变量进行查找，这类问题往往通过暴力（双循环）可以解出，而采用双指针相当于用空间换取时间，省略双层循环中重复的部分。

本帖介绍双指针的四个典例，具体如下：

目录

一.双指针算法解决单词分割

二.双指针算法解决最长不重复子列

三.双指针算法实现平方数组排序

四.双指针解决柱子间最大面积

---

一.双指针算法解决单词分割

从终端输入一段字符串，单词之间按照空格分开，实现对单词的划分输出。

思路：使用双指针i and j，i负责找到单词的头部，而j负责找到单词的尾部。每找到一个单词即刻输出，能够降低代码的复杂度。

（具体解析请看代码注释）

#include <iostream>
#include <string.h>
using namespace std;
 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
 
int main(int argc, char** argv) 
{
	char str[100];
	//字符型的字符串（C语言风格） 
	gets(str);
	//读取字符串 
	int n=strlen(str);
	//获取字符串长度 
	for(int i=0;i<n;i++)
	{
		int j=i;
		//从当前首字母开始找 
		while(j<n&&str[j]!=' ') 
			j++;
			//相当于找到空格的前一位 
		for(int k=i;k<j;k++)
			cout<<str[k];
			//注意，由于此刻j指向空格，所以下标应该小于j而不能包含j 
		cout<<endl;
		i=j;
		//此刻i等于j，即指向空格，因此i++后直接指向下一个单词的首字母，依次类推 
		
	}
	return 0;
}

运行结果如下图：

二.双指针算法解决最长不重复子列

 从终端读入一段数字，统计不出现重复数字的最长子列长度：

例如：1 2 2 3 5 6 6，最长不重复子列的长度是4。

代码思路：

        如果是单纯的暴力枚举，则需要两层循环，一个枚举起点，另一个枚举终点。通过双指针优化复杂度：统计每一个数字出现的次数，当次数大于1时，则说明一定是当前新统计的数字重复了！此刻，我们只需要从前往后遍历，直到没有大于1的元素，停止遍历，记录此刻两个指针之间的距离，并更新当前最大距离。

具体代码如下：

#include <iostream>
using namespace std;
 
const int N=100000;
//测试用例上限为100000 
int n;
int a[N],s[N];
//a数组用于存放目标数组，而s数组负责统计当前数字一共出现的次数
//当s数组中有一位>1,则说明有重复的元素，需要依次递减
//直到全部元素为0，再输出当前最大长度的值 
int main(int argc, char** argv) 
{
	int res=0;
	//统计最大值 
	cin>>n;
	for(int i=0;i<=n-1;i++)
		cin>>a[i]; 
		
	for(int i=0,j=0;i<=n-1;i++)
	{
		//此处枚举的是终点 
		s[a[i]]++;
		//用a[i]的值作为下标，此处
		while(s[a[i]]>1)
		//加入新的a[i]后，如果当前元素的统计大于1，则说明重复 
		{
			s[a[j]]--;
			j++; 
			//从第0项开始逐个减1，当大于1的部分被减去后小于1，则循环结束
			//此时数列中必然没有重复的数字 
		} 
		res=max(res,i-j+1);
		//计算此时ij之间的距离，与之前的最大值作比较 	 
	}
	cout<<res<<endl;
	//输出最后的最大值 
	return 0;
}

三.双指针算法实现平方数组排序

 对于一个含有负数的有序数组，要求保证在该数组每个元素平方后仍然保证有序。

如：-7 1 6 6 ，则平方后的排序应该是：1 36 36 49

一个简单的想法是，将所有元素平方后再进行排序，这是一种比较暴力的做法，复杂度取决于排序算法的复杂度。

然而仔细思考一下不难发现，平方的本质就是二倍的绝对值，而绝对值是一种计算模长的方式：对对于向量来说，不考虑方向的情况下模长即为大小。对应本题，换句话说，由于原数组本身为有序数组，平方后的最大值一定出现在原数组的两端——最小的负数和最大的正数之间。

因此我们可以采用双指针算法，从数组两侧开始寻找，左右指针指向元素大的先压入新的数组，然后向中间移动指针，再进行下一轮比较；直到两指针相遇时结束~ 

具体的C++代码如下：

#include <iostream>
#include <vector>
 
using namespace std; 
 
int main(int argc, char** argv) {
	int num=0;
	vector<int> V;
	cout<<"请输入数组中元素的个数："<<endl;
	cin>>num;
	for(int i=1;i<=num;i++)
	{
		int temp=0;
		cin>>temp;
		V.push_back(temp);
	}
	cout<<"原数组为："; 
	for(vector<int>::iterator it=V.begin();it!=V.end();it++)
		cout<<(*it)<<" ";
	cout<<endl;
	
	int it1=0,it2=num-1;
	//分别指向头部和尾部
	vector<int> N;
	for(int i=1;i<=num;i++)
		N.push_back(0);
	//开辟新的数组用于存放平方后的数组 
	while(it1<=it2)
	{   //指针未相遇时持续循环 
		if(V[it1]*V[it1]>=V[it2]*V[it2])
		{
			//大者先入数组 
			int temp1=V[it1]*V[it1]; 
			N[num-1]=temp1;
			//直接将大的存在最后面，省去排序的过程 
			it1++;
			//指针向中间移动 
			num--;
			//下标要向前移动 
		}
		else if(V[it2]*V[it2]>V[it1]*V[it1])
		{
			int temp2=V[it2]*V[it2];
			N[num-1]=temp2;
			it2--;
			num--;
			//同理 
		}
	} 
	cout<<"升序后的平方和数组为："<<endl;
	for(vector<int>::iterator it=N.begin();it!=N.end();it++)
		cout<<(*it)<<" ";
	cout<<endl;
	return 0;
}

运行结果如下：

再加一组测试用例：-7 -3 1 1 5 9

 答案符合预期~

四.双指针解决柱子间最大面积

  已知现在有几根柱子成有序排列，求出两根柱子之间围成面积的最大值。

         不难想到，只需要将每两个柱子之间的面积计算一次并找出最大值，即可找到答案，但采用双指针法可以有效降低重复计算：从数组的两侧开始移动左右两个指针，首先计算当前面积，由于面积由两根柱子之间的短者决定，因此不难想出：下次移动较长的柱子所对应的指针是没有意义的，故我们应该移动较短侧的指针，如果移动后值变大则更新最大值，否则继续向前移动，直至两指针相遇——通过此种方法的复杂度为o（n）。

实现的代码如下：

#include <iostream>
#include <vector>
using namespace std;
 
int main(int argc, char** argv) {
	int num=0;
	vector<int> V;
	cout<<"请输入柱子的个数："<<endl;
	cin>>num;
	for(int i=1;i<=num;i++)
	{
		int temp=0;
		cin>>temp;
		V.push_back(temp);
	}
	cout<<"用户读入的数据为："; 
	for(vector<int>::iterator it=V.begin();it!=V.end();it++)
		cout<<(*it)<<" ";
	cout<<endl;
	cout<<endl;
	 
	int it1=0;
	int it2=num-1;
	//分别定义指向头尾的指针
	int max=0;
	while(it1!=it2)
	{
		cout<<"当前指针下标为："<<it1<<" and "<<it2<<endl;
		if(V[it1]>V[it2])
		{
			cout<<"左指针更大一些"<<endl;
			int maxt=(it2-it1)*V[it2];
			if(maxt>max)
				max=maxt;
			cout<<"本次操作的面积为："<<maxt<<endl;
			cout<<"当前操作的最大值为："<<max<<endl;
			it2--; 
		}
		else if(V[it2]>V[it1])
		{
			cout<<"右指针更大一些"<<endl;
			int maxt=(it2-it1)*V[it1];
			if(maxt>max)
				max=maxt;
			cout<<"本次操作的面积为："<<maxt<<endl;
			cout<<"累计操作的最大值为："<<max<<endl;
			it1++; 
		}
		cout<<endl;
	} 
	cout<<"求得的最大面积为："<<max<<endl; 
	return 0;
}

 通过手算不难发现上述用例结果为6。

第二个用例，手算结果为12。

最后再来一个更长的用例，手算结果为42。

 此处发现了一个bug：就是源代码未考虑两个指针相等的情况。此处规定：当两指针相等时，对比两指针靠内侧的的下一位大小，如果左边大就移动左边，反之则右边，如果还相同则可以任选。

具体代码如下：

else if(V[it1]==V[it2])
		{
			cout<<"两个指针一样大"<<endl;
			int maxt=(it2-it1)*V[it1];
			if(maxt>max)
				max=maxt;
			cout<<"本次操作的面积为："<<maxt<<endl;
			cout<<"累计操作的最大值为："<<max<<endl;
			if(V[it1+1]>V[it2-1])
				it1++;
			else if(V[it1+1]<=V[it2-1])
				it2--;
			//判断两侧的下一位谁大，谁大移动谁
			//对于下一位还相同的情况，则可以任选一侧，此处选的是右侧 
		}

 结果与预期一致。