给定一个整数 x 和一个由 N 个不同整数组成的排序数组 a，设计一个线性时间算法来确定是否存在两个不同的索引 i 和 j 使得 a[i] + a[j] == x
问问题
41702 次
12 回答
40
这是子集和问题的类型
这是我的解决方案。不知道是不是早知道。想象一下两个变量 i 和 j 的函数的 3D 图：
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)
于 2012-08-13T04:20:01.003 回答
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;
}
于 2012-08-13T04:15:14.203 回答
2
- 首先通过搜索 > ceil(x/2) 的第一个值。让我们将此值称为 L。
- 从 L 的索引开始，向后搜索，直到找到与总和匹配的另一个操作数。
它是 2*n ~ O(n)
这我们可以扩展到二分搜索。
使用二分搜索来搜索一个元素，使得我们找到 L，使得 L 为 min(elements in a > ceil(x/2))。
对 R 执行相同操作，但现在将 L 作为数组中可搜索元素的最大大小。
这种方法是 2*log(n)。
于 2012-08-13T20:37:37.503 回答
2
这是一个使用 Dictionary 数据结构和数字补码的 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
于 2016-06-22T00:53:29.417 回答
2
鉴于数组已排序（WLOG 以降序排列），我们可以执行以下操作： 算法 A_1：给定 (a_1,...,a_n,m)，a_1<...,<a_n。将一个指针放在列表的顶部，一个放在底部。计算两个指针所在的总和。如果总和大于 m，则将上面的指针向下移动。如果总和小于 m，则将下指针向上移动。如果一个指针在另一个指针上（这里我们假设每个数字只能使用一次），报告 unsat。否则，（将找到相等的总和），报告 sat。
很明显，这是 O(n)，因为计算的和的最大数量正好是 n。正确性的证明留作练习。
这只是 SUBSET-SUM 的 Horowitz 和 Sahni (1974) 算法的一个子程序。（但是，请注意，几乎所有通用 SS 算法都包含这样的例程，Schroeppel, Shamir (1981), Howgrave-Graham_Joux (2010), Becker-Joux (2011)。）
如果给定一个无序列表，实现这个算法将是 O(nlogn)，因为我们可以使用 Mergesort 对列表进行排序，然后应用 A_1。
于 2021-06-19T14:39:17.257 回答
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;
}
于 2015-01-27T15:56:16.477 回答
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;
}
于 2015-05-12T18:23:22.287 回答
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";
于 2016-07-08T06:20:44.960 回答
0
归功于狮子座
他在java中的解决方案，如果你想试一试
我删除了返回，所以如果数组已排序，但允许重复，它仍然给出对
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;
}
于 2018-03-07T22:45:26.700 回答
0
解决方案
- 我们需要数组来存储索引
- 检查数组是否为空或包含少于 2 个元素
- 定义数组的起点和终点
- 迭代直到满足条件
- 检查总和是否等于目标。如果是，请获取索引。
- 如果不满足条件，则根据总和值向左或向右遍历
- 向右移动
- 向左移动
欲了解更多信息：[ http://www.prathapkudupublog.com/2017/05/two-sum-ii-input-array-is-sorted.html
于 2017-05-12T22:10:34.363 回答
0
这是一个线性时间复杂度解 O(n) 时间 O(1) 空间
public void twoSum(int[] arr){
if(arr.length < 2) return;
int max = arr[0] + arr[1];
int bigger = Math.max(arr[0], arr[1]);
int smaller = Math.min(arr[0], arr[1]);
int biggerIndex = 0;
int smallerIndex = 0;
for(int i = 2 ; i < arr.length ; i++){
if(arr[i] + bigger <= max){ continue;}
else{
if(arr[i] > bigger){
smaller = bigger;
bigger = arr[i];
biggerIndex = i;
}else if(arr[i] > smaller)
{
smaller = arr[i];
smallerIndex = i;
}
max = bigger + smaller;
}
}
System.out.println("Biggest sum is: " + max + "with indices ["+biggerIndex+","+smallerIndex+"]");
}
于 2017-01-17T09:40:40.240 回答
0
注意：代码是我的，但测试文件不是。此外，哈希函数的这个想法来自网络上的各种阅读。
Scala 中的一个实现。它对值使用 hashMap 和自定义（但简单）映射。我同意它没有利用初始数组的排序特性。
哈希函数
我通过将每个值除以 10000 来固定存储桶大小。该数字可能会有所不同，具体取决于您想要的存储桶大小，可以根据输入范围进行优化。
例如，键 1 负责从 1 到 9 的所有整数。
对搜索范围的影响
这意味着，对于当前值n，您正在寻找补码c例如n + c = x（x是您试图找到 2-SUM 的元素），有只有 3 个可能的桶，其中补码可以是：
- -钥匙
- -键 + 1
- -键 - 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
}
}
}
于 2015-08-24T01:16:56.037 回答