题目:数组A由1000W个随机正整数(int)组成，设计算法，给定整数n，在A中找出符合如下等式:n=a+b的a和b，说明算法思路以及时间复杂度是多少?
方法一:
设一个辅助容器temp长度为N+1
遍历A,将A中小于等于N的数字填入temp,具体的表现在temp中就是,其下标就是其位置元素的大小
填完之后,遍历temp,找出i位置和n-i位置不为空的,而且这里要防止重复
代码:
public void printNequalAB(int[] arr,int N){
//数组A由1000W个随机正整数(int)组成，设计算法，给定整数n，
// 在A中找出符合如下等式:n=a+b的a和b，说明算法思路以及时间复杂度是多少?
if (arr==null||N<0){
return;
}
int[] temp=new int[N+1]; //可以放0~N上闭区间的数
for(int i=0;i<arr.length;i++){
if (arr[i]<=N){
if (temp[arr[i]]!=1){
temp[arr[i]]=1;
}
}
}//向temp里注入小于N的数,以其数字大小找到其位置
for(int i=0;i<temp.length;i++){
if (temp[i]==1&&temp[N-i]==1&&(i<N-i)){//(i<N-i) 去重处理
System.out.println(i+" "+(N-i));
}
}
}
方法二:双指针法
先排序
然后定义两个指针,根据两端数值大小移动两个指针
前面写过一样的题目了,这里就不重复写了,可以参考下面链接https://www.jianshu.com/p/8985b009dacd
方法三: 利用hash的存取速度为O(1)的特性
1.将数组A中的数据，存入Hash表；
2.遍历A数组，假设当前取到的值为a = A[i],则b = x-A[i]；
3.在Hash表中查找b，如果存在则返回，否则继续2-3，直至找到符合要求的解。
时间复杂度O(n)
