检查给定数字是否是2个数组中两个数字的总和

Question

我试过蛮力的方式:

#include <stdio.h>

int sum(int a [],int b[], int m);

int main (void)
{
  int a [] = {1,2,3,4,5};
  int b [] = {4,3,5,2,6};
  int i;
  printf("Enter to find a given number:\n");
  scanf("%d",&i);
  printf("%s\n",sum(a,b,i) ? "True":"False");
  return 0;

}

int sum(int a[], int b[],int m)
{
  int i=0,j=0;

  for (i=0;i<=sizeof(a)/sizeof(int)+1;i++)
   for(j=0;j<=sizeof(b)/sizeof(int)+1;j++)
    if (a[i]+b[j]==m)
     return 1;

  return 0;
}

你可以看到运行时间是O(n ^ 2),有没有巧妙的方法来最小化这个？

Answer 1

更快的解决方案(O(n))是使用哈希表.只需将第一个数组中的所有元素放入其中,然后迭代第二个数组,检查目标数与当前数之间的差异是否在哈希表中.这是C++中的实现:

int main(){
    int a [5] = {1,2,3,4,5};
    int b [5] = {4,3,5,2,6};
    int m;
    printf("Enter to find a given number:\n");
    scanf("%d",&m);

    set<int> s;
    for (int i = 0; i < 5; i++)
        s.insert(a[i]);

    for (int i = 0; i < 5; i++)
        if (s.count(m-b[i]) > 0) {
            printf("True\n");
            return 0;
        }

    printf("False\n");
}