发现两个元素，以便和等于给定值 [英] find two elements so sum is equal to given value

问题描述

两套'n'个数列A和B从A之所以选择一种元素和一个选自B，使得总和等于一给定值，VAL

我已经得到了解决方案：

  

我们可以散列集合A与B的元素，并为您在集合A中的每一个元素VAL-改编[I]是否存在于B组与否的哈希值。这将需要O（n）时间及O（n）的空间   可有与空间o一个更好的解决方案（1），时间为O（n）？

解决方案

当你有两个数组没有排序，你没有其他选择，只能看每个元素一个接一个。所以，你不能低于 O（N）运行时间。我认为你正在使用的方法是确定的。

阅读这些相关文章：

<一个href="http://stackoverflow.com/questions/3815116/given-two-arrays-a-and-b-find-all-pairs-of-elements-a1-b1-such-that-a1-belong">Given两个数组a和b .Find所有元素对（A1，B1），使得A1属于阵列A和B1属于数组b的总和A1 + B1 = K

查找的数组总和两个元素ķ

Two sets of 'n' numbers are given A and B. Chose one element from A and one from B such that the sum is equal to a given value, 'val'.

I have got the solution as:

We can hash the elements of Set A and Set B and check for every element in set A whether val-arr[i] exists in the hash of Set B or not. This would take O(n) time and O(n) space Can there be a better solutions with space as O(1) and time O(n)?

解决方案

As you have both the arrays NOT sorted, you have NO other option but look at every element one-by-one. So, you cannot get below O(n) running time. I think the approach you are using is ok.

Read these related posts:

Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k

Find two elements in an array that sum to k

这篇关于发现两个元素，以便和等于给定值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！