5
17
2016
0

求数组中和为给定值的元素对

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

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记录即可。记得排序

Category: 总结 | Tags: 技巧 二分 点分治 | Read Count: 659

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com