Ryan_<

给定一个数组，在数组中找到满足条件的两个数，使得这两个数的和为某一给定的值。如果有多对数，只输出一对即可。

1、NC枚举，显然O(n^2)

先sort使数组变为有序：

2、满足单调性，枚举一个位置+最基础的二分查找 O(nlogn+nlogn)

//二分查找:
typedef pair<int,int> pa;
int binarySearch(int a[],int l,int r,int val)
{
	while(l<r){
		int mid=l+(r-l)/2;
		if(a[mid]==val) return mid; 
		if(a[mid]>val) r=mid-1;
		else l=mid+1;
	}
	return -1;
}
pa getsumNum(int a[],int n,int sum)
{
	for(int i=1;i<=n;i++){
		int pos=binarySearch(a,i+1,n,sum-a[i]);
		if(pos==-1) continue;
		return make_pair(i,pos);
	}
	return make_pair(-1,-1);
} 

3、双指针法，常用于预处理 O(n+nlogn)

复杂度取决于排序

typedef pair<int,int> pa;
pa getSumNum(int a[],int n,int sum)//找不到则返回(-1,-1) 
{
	int i=1,j=n-1;
	while(i<j){
		if(a[i]+a[j]==sum) return make_pair(i,j);
		else if(a[i]+a[j]<sum) i++;
		else j--;
	}
	return make_pair(-1,-1);
}

尝试一下for循环的写法：

typedef pair<int,int> pa;
pa GetSumNum(int a[],int n,int sum)
{
	for(int i=1,j=n-1;i<j;){
		if(a[i]+a[j]==sum) return make_pair(i,j);
		else if(a[i]+a[j]<sum) i++;
		else j--;
	}
	return make_pair(-1,-1);
} 

这一简单的思想也可用于树问题的处理：

给定一棵有根树，根为p，问有多少点对(u, v)，使得u,v 距离大于等于W。

改为cnt记录即可。记得排序