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

问题描述

给定的整数x和一个排序后的数组一个N个不同的整数，设计一个线性时间算法，以确定是否存在两个不同的索引i和j，使得[I] +一[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

推荐答案

想象一下，两个变量的函数3D图i和j：

Imagine 3D plot of function of two variables i and j:

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

对于每个我有这样Ĵ的 A [I] + A [ J] 最接近 X 。所有这些（I，J）对形成的最接近到-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 << i << " " << j << endl;  
        return;
    }
    if (sum > x)    j--;
    else            i++;
    if (i > j) break;
 }  
 cout << " not found\n";

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