题目:数组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)