2-SUM 的线性时间算法 [英] Linear time algorithm for 2-SUM

问题描述

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

Given an integer x and a sorted array a of N distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i] + a[j] == x

推荐答案

这是子集求和问题的类型

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

Here is my solution. I don't know if it was known earlier or not. Imagine 3D plot of function of two variables i and j:

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

对于每个 i 都有这样的 j 使得 a[i]+a[j] 最接近 x代码>.所有这些 (i,j) 对形成 closest-to-x 行.我们只需要沿着这条线走，寻找a[i]+a[j] == x:

For every i there is such j that a[i]+a[j] is closest to x. All these (i,j) pairs form closest-to-x line. We just need to walk along this line and look for 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
";

复杂度:O(n)

这篇关于2-SUM 的线性时间算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！