在数组中查找总和为 k 的两个元素 [英] Find two elements in an array that sum to k
问题描述
可能的重复:
给定两个数组 a 和 b .找出所有元素对 (a1,b1),使得 a1 属于数组 A,b1 属于数组 B,其总和 a1+b1 = k .
给定:一个未排序的整数数组 A
输入:一个整数k
Given : An unsorted array A
of integers
Input : An integer k
输出:所有两个元素集合,每个集合中元素的总和等于k
,O(n).
Output : All the two element set with sum of elements in each set equal to k
in O(n).
示例:
A = {3,4,5,1,4,2}
输入:6
输出:{3,3}, {5,1}, {4,2}
注意:我知道一个 O(n logn) 解决方案,但这需要对数组进行排序.有什么办法可以在 O(n) 中解决这个问题.可以使用非平凡的 C++ 数据结构,即没有空间限制
Note : I know an O(n logn) solution but that would require to have the array sorted. Is there any way by which this problem can be solved in O(n). An non-trivial C++ data structure can be used i.e there's no bound on space
推荐答案
制作一个恒定时间查找表(哈希),以便您可以查看数组中是否包含特定整数 (O(n)).然后,对于数组中的每个元素,查看是否包含 k-A[i]
.对于每个元素,这需要恒定的时间,因此总共需要 O(n) 时间.这假设元素是不同的;让它与重复元素一起工作并不困难.
Make a constant-time lookup table (hash) so you can see if a particular integer is included in your array (O(n)). Then, for each element in the array, see if k-A[i]
is included. This takes constant time for each element, so a total of O(n) time. This assumes the elements are distinct; it is not difficult to make it work with repeating elements.
这篇关于在数组中查找总和为 k 的两个元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!