检查给定数字是否是 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");
}