Я попробовал альтернативный подход к проблеме 3sum : с помощью массива найти все триплеты, которые суммируют до заданного числа.
В основном подход такой: сортировка массива.Как только пара элементов (скажем, A [i] и A [j]) выбрана, для третьего элемента выполняется двоичный поиск [с использованием функции equal_range ].Индекс, следующий за последним из соответствующих элементов, сохраняется в переменной 'c'.Так как A [j + 1]> A [j], мы должны искать только до и исключая индекс c (так как числа в индексе c и далее определенно будут суммироваться больше, чем целевая сумма).Для случая j = i + 1 мы сохраняем индекс конца как 'd' и делаем c = d.Для следующего значения i, когда j = i + 1, нам нужно искать только до и исключая индекс d.
Реализация C ++:
int sum3(vector<int>& A,int sum)
{
int count=0, n=A.size();
sort(A.begin(),A.end());
int c=n, d=n; //initialize c and d to array length
pair < vector<int>::iterator, vector<int>::iterator > p;
for (int i=0; i<n-2; i++)
{
for (int j=i+1; j<n-1; j++)
{
if(j == i+1)
{
p=equal_range (A.begin()+j+1, A.begin()+d, sum-A[i]-A[j]);
d = p.second - A.begin();
if(d==n+1) d--;
c=d;
}
else
{
p=equal_range (A.begin()+j+1, A.begin()+c, sum-A[i]-A[j]);
c = p.second - A.begin();
if(c==n+1) c--;
}
count += p.second-p.first;
for (auto it=p.first; it != p.second; ++it)
cout<<A[i]<<' '<<A[j]<<' '<<*it<<'\n';
}
}
return count;
}
int main() //driver function for testing
{
vector <int> A = {4,3,2,6,4,3,2,6,4,5,7,3,4,6,2,3,4,5};
int sum = 17;
cout << sum3(A,sum) << endl;
return 0;
}
Я не могу определить время верхней границы, необходимое для этого алгоритма.Я понимаю, что наихудший сценарий будет, когда целевая сумма недостижимо велика.
Мои вычисления дают что-то вроде:
Для i = 0, нет.бинарных поисков: lg (n-2) + lg (n-3) + ... + lg (1)
для i = 1, lg (n-3) + lg (n-4)+ ... + lg (1)
...
...
...
Для i = n-3, lg(1)
Итак, lg ((n-2)!) + Lg ((n-3)!) + ... + lg (1!) = Lg (1 ^ n * 2 ^(n-1) 3 ^ (n-2) ... * (n-1) ^ 2 * n ^ 1)
Но как вывести оценку O (n)из этого выражения?