算法-已知一个数组int a={2,3,4,5,7,9,12,14,15},m=14,a中元素2和12满足条件。要求时间复杂度O(n).

Question

已知一个数组int a[]={a1,a2,a3,...an}，与一个数m,求数组中两个元素ai,aj使它们的和等于m。例如a[]={2,3,4,5,7,9,12,14,15},m=14,a中元素2和12满足条件。要求时间复杂度O(n).

Answer 1

//假设A里边的数大于等于0,且假设A的两两元素不同,先想到这里，至于重复元素的情况回来想，先出去了
int a={2,3,4,5,7,9,12,14,15};
int l_a=sizeof(a)/(sizeof(int));
int pro[m+1]={-1};
int i;
int tp=(m%2==0)?m>>1,-1;
for(i=0；i<l_a;i++)
{
pro[a[i]]=i;
}

for(i=0；i<m+1;i++)
{
if(pro[i]>0 && pro[m-i]>0)
｛
if(tp>0 && i!=tp) printf("a[%d] + a[%d] =%dn",pro[i],pro[m-i]);
｝
}

Answer 2

从这个题目上看，这个数组应该是已经按照升序排好序的吧？这样就很方便处理了。如果没有排序，则先排序，再进行下面的算法。
算法过程如下：
1.设置两个指针，一个指向该数组的首元素start，一个指向该数组的末元素end。
2.判断两个指针所指元素的和与给定数字m的大小关系：
1）如果相等，则直接返回true，因为已经找到。
2）如果指针所指元素之和大于m，则将end指针前移一位，继续比较；
3）如果指针所指元素之和小于m，则将start指针后移一位，继续比较；
4）如果某次指针移位之后，start位置位于end之后，就直接返回false，因为找不到满足要求的数字了。
算法总时间复杂度O(n).示例代码如下：

#include <iostream>
using namespace std;

int a[] = {2, 3, 4, 5, 7, 9, 12, 14, 15};

bool find(int num, int* start, int* end)
{
while(1)
{
if(a[*start] + a[*end] == num)
{
return true;
} else if (a[*start] + a[*end] < num)
{
(*start)++;
} else if (a[*start] + a[*end] > num)
{
(*end)--;
}

if (*start > *end)
{
return false;
}
}
}

int main()
{
int start;
int end;
int num;
while(1)
{
cout << "Please input the num:";
cin >> num;
if (num == 0)
{
break;
}

start = 0;
end = 8;
if (find(num, &start, &end))
{
cout << "Find them!" << endl;
cout << "The first num is " << a[start] << ", at index of " << start << endl;
cout << "The second num is " << a[end] << ", at index of " << end << endl;
} else
{
cout << "No find!" << endl;
}
}
return 0;
}

可以循环输入m值，然后判断是否存在满足条件的数字。如果存在，则会输出这两个元素和它们在数组中的位置。如果不存在，就会返回查找失败。
如果想要退出程序，只需要给m输入0值即可。

Answer 3

也有一个O(n)的想法
由

 int a[10]={2,3,4,5,7,9,12,14,15};

算出来(a[9]+b[0]=14,a[8]+b[1]=14....)

 int b[10] = {-1, 0, 2, 5, 7, 9, 10, 11, 12};

由于数组a,b都排好顺序,所以

 #include<stdio.h>

int main()
{
int a[10] = {2,3,4,5,7,9,12,14,15};
int b[10] = {-1, 0, 2, 5, 7, 9, 10, 11, 12};
int i=0, j=0, k=0;
while(k<=20) {
k++;
if (i>=10 || j >= 10) {
continue;
}

if (a[i] > (14/2)) {
continue;
}

if (a[i] > b[j]) {
j++;
}
if (a[i] < b [j]) {
i++;
}

if (a[i] == b[j]) {
printf("%d, %dn", a[i], (14-b[j]));
i++;
j++;
}
}
}