سوال ۶۲ کنکور ارشد علوم کامپیوتر ۱۴۰۴

This is the classic 3SUM (counting variant): count index triples $(i,j,k)$ with $A[i]+A[j]+A[k]=x$.

Naive bound. Three nested loops give $\Theta(n^{3})$ — that is option 3, not optimal.

The standard $\Theta(n^{2})$ algorithm.

1. Sort the array once: $\Theta(n\log n)$.
2. Fix the first element $A[i]$ (loop over $i$, $n$ iterations). The subproblem becomes: count pairs $(j,k)$ with $A[j]+A[k] = x - A[i].$
3. Solve each pair-count (a 2SUM on a sorted array) with a two-pointer sweep in $\Theta(n)$: a left pointer $\ell$ and a right pointer $r$ move inward — if the sum is too small advance $\ell$, if too large retreat $r$, and on a hit count the matches. Each pointer crosses the array once, so $\Theta(n)$ per fixed $i$.

Total: $\Theta(n\log n) + n\cdot\Theta(n) = \Theta(n^{2}).$

Negative numbers cause no trouble: sorting and the two-pointer monotonicity argument only need a total order, which the integers have. Hashing gives the same $\Theta(n^{2})$ expected bound but adds nothing asymptotically.

Why not lower? 3SUM is conjectured to have no truly sub-$n^{2}$ (e.g. $O(n^{2-\varepsilon})$) algorithm — the 3SUM conjecture. So within the tools of a standard algorithms course, $\Theta(n^{2})$ is the optimal achievable order, and $n\log n$ (option 1) is not attainable.

Hence the optimal order is $n^{2}$ — option 2.

Exam trick: Whenever you must count/find $k$ items summing to a target, sort once and reduce dimension with two pointers: 2SUM drops to $\Theta(n)$, 3SUM to $\Theta(n^{2})$, kSUM to $\Theta(n^{k-1})$ — always one factor of $n$ below the brute force.