algorithm - 2-SUM 的线性时间算法

Question

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

Answer 1

这是 Subset sum problem 的类型

这是我的解决方案。不知道是不是早知道了。想象一下两个变量 i 和 j 的函数的 3D 图:

sum(i,j) = a[i]+a[j]

对于每个 i 都有这样的 j 使得 a[i]+a[j] 最接近 x。所有这些 (i,j) 对形成 closest-to-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)