首页 > 试题广场 >

在包含N 个正整数的数组中快速找出两个数字，让这两个数字之和

[问答题]

查找数对
在包含N 个正整数的数组中快速找出两个数字，让这两个数字之和等于M，返回两个数字中的任一个即可，如找不到这返回-1。
1)请完成find 的代码实现（C++或Java），尽可能提高算法的时间空间复杂度。
C++:

int find(int M, int N, int[] a) {
…
}

Java:

int find(int M, int[] a) {
…
}

例如：
当输入为
M=11 N=9
a = {
8, 4, 1, 6, 7, 4, 9, 6, 4}

返回为4 或7

2)设计测试用例测试find 函数

查看答案及解析

推荐

沧岛

int find(int M, int N, int[] a) {
Arrays.sort(a);//排序  int i=0,j=N-1;

　　while(i!=j){

           if(a[i]+a[j]==M){

　　　　　System.out.print(a[i]+"--"+a[j]);

                 break;

　　　　}

　　　　a[i]+a[j]>M?j--:i++;

　　} }

原来的测试用例就行

编辑于 2015-02-09 09:30:55 回复(0)

尽力而为

public int find(int M, int[] a) {
        int len = a.length;
        if(len == 0)
            return -1;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(i != j){
                    int sum = a[i] + a[j];
                    if(sum == M){
                        return a[i];
                    }
                }
            }
        }
        return -1;
    }

发表于 2015-08-30 21:53:56 回复(0)

kaka2008

1.首先排序，变成有序数组这里就使用简单的选择排序
2.在有序数组中找两个数和为M 使用两个指针，一个从开头向后遍历，一个从结尾向前遍历。
因为有序如果两个值相加小于M则begin加1 如果大于M则end减1 只需要遍历一次时间复杂度为o(n)

///找出有序数组a中两数和为M的数
int find1(int M,int N,int a[] ){
  int * begin1=a;
  int * end1=a+N-1;
  while(begin1<end1){
  if(*begin1+ *end1<M){
    begin1++;
  }else if(*begin1+*end1>M) {
    end1--;
  }else{
    return *begin1;
    }
  }
    return -1;
}

///简单选择排序
void simpleSelectSort(int a[],int n){
    for(int i=0;i<n;i++){
            int min1=i;
        for(int j=i+1;j<n;j++){
            if(a[j]<a[min1]){
                min1=j;
            }
        }
        if(min1!=i){
        int temp=a[i];
        a[i]=a[min1];
        a[min1]=temp;
        }
    }
}

发表于 2015-05-18 17:12:55 回复(0)

提交观点

问题信息

数组小米集团查找

上传者：未央

难度：

3条回答 5收藏 9884浏览

在包含N 个正整数的数组中快速找出两个数字，让这两个数字之和

问题信息

热门推荐

相关试题