10.Two Pointers算法重难点剖析

1.two pointers

以一个例子引入：给定一个递增的正整数序列和一个正整数M，求序列中的两个不同位置的数a和b，使得它们的和恰好为M，输出所有满足条件的方案。例如给定序列{1，2，3，4，5，
6}和正整数M=8，就存在2+6=8与3+5=8成立。
本题的一个最直观的想法是，使用二重循环枚举序列中的整数a和b，判断它们的和是否为M，如果是，输出方案；如果不是，则继续枚举。代码如下：

for(int i=0;i<n;i++){
	for(intj=i+1;j<n;j++){
		if(a[i]+a[j]==M){
			printf("%d %d\n",a[i],a[j]);
		}
	}
}

<mark>这种做法的时间复杂度为O（n2），对n在105的规模时是不可承受的。</mark>

以下是优化算法：

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a[6]={1,2,3,4,5,6}; //升序数组
	int x=6; //相加=x
	int i=0,j=5;   //i=0 j=n-1 n位数组长度
	while(i<j)
	{
		if(a[i]+a[j]==x) 
		{
			cout<<a[i]<<"+"<<a[j]<<"="<<x<<endl;
			i++;
			j--;
		}
		else if(a[i]+a[j]<x) i++;
		else j--;
	} 
	return 0;
}

2.序列合并优化

#include <bits/stdc++.h>
using namespace std;
int a[3]={1,2,3},b[3]={1,4,5},c[100]={};  //必须采用全局数组 否则就需要指针 
int hebing(int a[],int b[],int c[],int n,int m)
{
	int index=0,i=0,j=0;
	while(i<n&&j<m)
	{
		if(a[i]<=b[j]) c[index++]=a[i++];
		else c[index++]=b[j++];
	}
	while(i<n) c[index++]=a[i++];
	while(j<m) c[index++]=b[j++];
	return index;   //返回合并后的数组的长度 
}
int main()
{
	for(int p=0;p<hebing(a,b,c,3,3);p++) cout<<c[p];
	return 0;
}