给定一个整数x和长度为N的升序排列的数组a，设计一个线性时间复杂度的算法来确定是否存在两个不同的索引i和j，使得a[i] + a[j]等于x。
13个回答
40
这是一个子集和问题
这是我的解决方案。我不知道它是否早已为人所知。想象一下一个关于两个变量i和j的函数的三维曲线图：
sum(i,j) = a[i]+a[j]
对于每个 i，都有一个这样的 j，使得 a[i]+a[j] 最接近 x。所有这些 (i,j) 对构成了最接近 x 的线。我们只需要沿着这条线走，并寻找 a[i]+a[j] == x：
int i = 0;
int j = lower_bound(a.begin(), a.end(), x) - a.begin();
while (j >= 0 && j < a.size() && i < a.size()) {
int sum = a[i]+a[j];
if (sum == x) {
cout << "found: " << i << " " << j << endl;
return;
}
if (sum > x) j--;
else i++;
if (i > j) break;
}
cout << " not found\n";
复杂度：O(n)
- Leonid Volnitsky
7
2这也可以工作，而且更有效率（由于数组的排序特性）。 - spotter
1太好了！但是负数怎么办？去掉
lower_bound 调用并设置 int j = a.size() - 1 可以是一个解决方案吗？ - fcatho考虑到这是一个主要涉及代码的答案，您可能需要提及编程语言，甚至在代码中进行注释（它的作用是什么/应该完成什么任务？）。我认为 @fcatho 的反对意见非常有道理：检查
lower_bound(a.begin(), a.end(), x-*a)。为什么不控制循环只使用 while (i < j)？另一种方法是使用 lower_bound(a.begin(), a.end(), x/2) 并从内向外工作 - 更复杂的循环控制。（刚滚动到其他答案 - 这是 Guru Devanla's 的回答）。 - greybeard1lower_bound 的时间复杂度是多少？ - Kalpesh Soni
1我不太理解“最接近”的概念，是指两点之间的距离吗？ - Abhijit Sarkar
显示剩余2条评论
13
从补集的角度思考。
遍历列表，在每个元素上计算到达X所需的数字。将数字和补数存入哈希表中。在遍历时检查数字或其补数是否在哈希表中。如果是，则找到了。
编辑：由于我有些时间，提供一些类似伪代码的代码。
boolean find(int[] array, int x) {
HashSet<Integer> s = new HashSet<Integer>();
for(int i = 0; i < array.length; i++) {
if (s.contains(array[i]) || s.contains(x-array[i])) {
return true;
}
s.add(array[i]);
s.add(x-array[i]);
}
return false;
}
- spotter
9
1哈希表的最坏情况创建时间复杂度为O(N^2)。 - Leonid Volnitsky
在C++中，map似乎通常不能像普通的哈希表一样工作？对于普通的哈希表，时间复杂度为O(1)到O(n)，而在C++中，insert和find的时间复杂度为**O(lgn)**。 "插入的复杂度（如果插入单个元素）通常是对数级别的，但如果给出提示并且给出的位置是最佳的，则摊销常数。" 链接 - zhenjie
@zhenjie std::map 通常是用红黑树实现的。 - mingyc
2你确定需要 s.add(array[i]); 吗？ - Bidou
你应该只检查 s.contains(x-array[i])，并在任何情况下都添加 s.add(array[i])，对吗？ - M4rk
显示剩余4条评论
4
考虑到数组是有序的（WLOG 降序），我们可以做以下事情：
算法 A_1： 给定 (a_1, ..., a_n, m)，其中 a_1 < ... < a_n。 在列表顶部和底部放置一个指针。 计算两个指针所在位置的和。 如果总和大于 m，则将上面的指针向下移动。 如果总和小于 m，则将下面的指针向上移动。 如果某个指针在另一个指针上（这里我们假设每个数字只能使用一次），则报告 unsat。 否则，（将找到一个等效的和），报告 sat。
很明显这是 O(n) 的，因为最多计算的和就是 n。正确性的证明留作练习。
这只是 Horowitz 和 Sahni (1974) 子集和算法的子程序。（但请注意，几乎所有通用的 SS 算法都包含这样一个例程，Schroeppel、Shamir（1981）、Howgrave-Graham_Joux（2010）、Becker-Joux（2011）。）
如果我们得到的是无序列表，实现此算法将是 O(nlogn)，因为我们可以使用归并排序对列表进行排序，然后应用 A_1。
- Z_22
1
此解决方案不像其他一些解决方案那样需要哈希表。 - qwr
2
这里是一种使用字典数据结构和数字补码的Python版本。它具有线性运行时间（N的顺序：O（N））：
def twoSum(N, x):
dict = {}
for i in range(len(N)):
complement = x - N[i]
if complement in dict:
return True
dict[N[i]] = i
return False
# Test
print twoSum([2, 7, 11, 15], 9) # True
print twoSum([2, 7, 11, 15], 3) # False
- Maksood
2
你确定这个能行吗？在
for循环之前，dict应该被填充。 - Maria Ines Parnisari你可以使用collections中的defaultdict而不是填充字典。 - subba
2
- 首先搜索第一个大于ceil(x/2)的值，并将其命名为L。
- 从L的索引开始向后搜索，直到找到匹配和的另一个操作数。
时间复杂度为2*n ~ O(n)。
我们可以将此扩展为二分搜索。
使用二分搜索查找元素，以便找到L，使得L是大于ceil(x/2)的最小元素。
对于R，执行相同的操作，但现在L是数组中可搜索元素的最大大小。
这种方法的时间复杂度为2*log(n)。
- grdvnl
3
这很不错，但你能否给我更多关于R是什么的细节？ - BlackJoker
对于二分查找，L代表左边，R代表右边；即子集的左右边界。 - mctylr
请注意，如果我们允许数组中有重复的数字（在面试中有时会出现这种情况），则此方法将无法正常工作。例如，当a=[13,13,22]和x=26时，您将得到值22来匹配第一次搜索（L=2），并且永远找不到R。 - Philippe Girolami
1
遍历该数组并将符合条件的数字及其索引保存到映射表中。该算法的时间复杂度为O（n）。
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> summap;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
summap[numbers[i]] = i;
}
for (int i = 0; i < numbers.size(); i++) {
int searched = target - numbers[i];
if (summap.find(searched) != summap.end()) {
result.push_back(i + 1);
result.push_back(summap[searched] + 1);
break;
}
}
return result;
}
- Evelyn Liu
2
1summap.find()会遍历映射中的所有元素，这可能会导致复杂度增加吗？ - Sai Manoj
summap.find具有O(log n)复杂度，因此该算法的复杂度是O(n log n)，而不是O(n)。 - Periata Breatta
0
感谢leonid
以下是他在Java中的解决方案，如果你想尝试一下
我去掉了return，所以如果数组已排序，但允许重复，它仍然会给出成对的结果
static boolean cpp(int[] a, int x) {
int i = 0;
int j = a.length - 1;
while (j >= 0 && j < a.length && i < a.length) {
int sum = a[i] + a[j];
if (sum == x) {
System.out.printf("found %s, %s \n", i, j);
// return true;
}
if (sum > x) j--;
else i++;
if (i > j) break;
}
System.out.println("not found");
return false;
}
- Kalpesh Soni
0
我会像这样将差异添加到 HashSet<T> 中：
public static bool Find(int[] array, int toReach)
{
HashSet<int> hashSet = new HashSet<int>();
foreach (int current in array)
{
if (hashSet.Contains(current))
{
return true;
}
hashSet.Add(toReach - current);
}
return false;
}
- Bidou
0
int[] b = new int[N];
for (int i = 0; i < N; i++)
{
b[i] = x - a[N -1 - i];
}
for (int i = 0, j = 0; i < N && j < N;)
if(a[i] == b[j])
{
cout << "found";
return;
} else if(a[i] < b[j])
i++;
else
j++;
cout << "not found";
- cseThomas
1
你想出了一个非常好的算法。如果 a[i] == b[j] 并且索引 i 等于索引 j，该怎么办？谢谢。 - Frank
0
注意：代码是我自己写的，但测试文件不是。此外，这个哈希函数的想法来自于网络上的各种阅读。
Scala实现。它使用了一个hashMap和一个自定义（但简单）的值映射。我同意它没有利用初始数组的排序特性。
哈希函数
我通过将每个值除以10000来固定桶大小。那个数字可能会有所变化，取决于您想要的桶的大小，这可以根据输入范围进行优化。
例如，键1负责所有从1到9的整数。
对搜索范围的影响
这意味着，对于当前值n，您正在寻找一个补充c，使得n + c = x（x是您试图找到2-SUM的元素），只有3个可能的桶中可以找到补充：
- -key
- -key + 1
- -key - 1
假设您的数字在以下形式的文件中：
0
1
10
10
-10
10000
-10000
10001
9999
-10001
-9999
10000
5000
5000
-5000
-1
1000
2000
-1000
-2000
这是Scala的实现
import scala.collection.mutable
import scala.io.Source
object TwoSumRed {
val usage = """
Usage: scala TwoSumRed.scala [filename]
"""
def main(args: Array[String]) {
val carte = createMap(args) match {
case None => return
case Some(m) => m
}
var t: Int = 1
carte.foreach {
case (bucket, values) => {
var toCheck: Array[Long] = Array[Long]()
if (carte.contains(-bucket)) {
toCheck = toCheck ++: carte(-bucket)
}
if (carte.contains(-bucket - 1)) {
toCheck = toCheck ++: carte(-bucket - 1)
}
if (carte.contains(-bucket + 1)) {
toCheck = toCheck ++: carte(-bucket + 1)
}
values.foreach { v =>
toCheck.foreach { c =>
if ((c + v) == t) {
println(s"$c and $v forms a 2-sum for $t")
return
}
}
}
}
}
}
def createMap(args: Array[String]): Option[mutable.HashMap[Int, Array[Long]]] = {
var carte: mutable.HashMap[Int,Array[Long]] = mutable.HashMap[Int,Array[Long]]()
if (args.length == 1) {
val filename = args.toList(0)
val lines: List[Long] = Source.fromFile(filename).getLines().map(_.toLong).toList
lines.foreach { l =>
val idx: Int = math.floor(l / 10000).toInt
if (carte.contains(idx)) {
carte(idx) = carte(idx) :+ l
} else {
carte += (idx -> Array[Long](l))
}
}
Some(carte)
} else {
println(usage)
None
}
}
}
- Bacon
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接