2-SUM的线性时间算法

Question

给定整数x和N个不同整数的排序数组a,设计线性时间算法以确定是否存在两个不同的索引i和j,使得a [i] + a [j] == x

Answer 1

这是子集和问题的类型

这是我的解决方案.我不知道它是否早先知道.想象一下两个变量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)

Answer 2

从补充的角度思考.

迭代列表,找出每个项目获得该数字所需的数字是多少.坚持编号和补充到哈希.迭代检查以查看数字或其补码是否为哈希值.如果是的话,找到了.

编辑:因为我有一些时间,一些伪代码.

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;
}