gpt4 book ai didi

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

转载 作者:太空狗 更新时间:2023-10-29 15:02:49 26 4
gpt4 key购买 nike

我尝试了蛮力方式:

#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),是否有任何聪明的方法可以将其最小化?

最佳答案

更快的可能解决方案 (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");
}

关于检查给定数字是否是 2 个数组中两个数字的总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9075469/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com