2-SUM的线性时间algorithm
给定一个整数x和一个有N个不同整数的有序数组a，devise一个线性时间algorithm来确定是否存在两个不同的索引i和j，使得a [i] + a [j] == x
这是子集总和问题的types
这是我的解决scheme。 我不知道是否早一点知道。 设想两个variablesi和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）
用补充来思考。
遍历列表，找出每个项目到达X的数量是多less。 把数字和补码合并成哈希。 同时迭代检查数字或其补码是否在散列。 如果是的话，find。
编辑：和我有一些时间，一些pseudo'ish代码。
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; }
- 首先search第一个值> ceil（x / 2）。 我们称这个值为L.
- 从L的索引开始，向后search，直到find匹配总和的另一个操作数。
它是2 * n〜O（n）
这我们可以扩展到二分查找。
-
使用二分searchsearch元素，以便findL，使得L是min（元素在> ceil（x / 2））中。
-
对R做相同的处理，但现在用L作为数组中可search元素的最大尺寸。
这种方法是2 * log（n）。
这是一个使用字典数据结构和数字补充的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
遍历数组并将合格的数字及其索引保存到地图中。 该algorithm的时间复杂度为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; }
我只是将差异添加到像这样的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; }
注意：代码是我的，但testing文件不是。 此外，这个散列函数的思想来自于网上的各种读物。
在Scala中的一个实现。 它使用一个哈希映射和一个自定义（但简单）的值映射。 我同意它不使用初始数组的sorting性质。
散列函数
我通过将每个值除以10000来固定存储桶大小。该数量可能会有所不同，具体取决于您想要的存储桶的大小，根据input范围可以使其最佳。
例如，关键字1负责从1到9的所有整数。
对search范围的影响
这意味着，对于一个当前值n ，你正在寻找一个补数c，例如n + c = x （ x是你试图find一个2-SUM的元素），有只有3个可能的桶，其中补充可以是：
- -键
- 键+ 1
- 键 – 1
假设您的号码是以下列forms的文件：
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 } } }
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";
这里是一个线性时间复杂性解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+"]");
}
解
- 我们需要数组来存储索引
- 检查数组是否为空或包含less于2个元素
- 定义数组的开始和结束点
- 迭代到满足条件
- 检查总和是否等于目标。 如果是的话，得到的指数。
- 如果不符合条件，则根据总和值向左或向右移动
- 遍历到右边
- 往左走
欲了解更多信息：[ http://www.prathapkudupublog.com/2017/05/two-sum-ii-input-array-is-sorted.html 
