سوال ۶۷ کنکور ارشد علوم کامپیوتر ۱۳۹۷

We must decide whether three indices exist with $x[i]^2 + x[j]^2 = x[k]^2.$

Reduce to a 3SUM-type problem. Define a new array $a$ of squares, $a[m] = x[m]^2 \quad (m = 1,\dots,n),$ computed in $O(n)$. The goal becomes: find indices with $a[i] + a[j] = a[k]$.

Sort the squares. Sort $a$ in $O(n\log n)$. Since all squares are non-negative, this is a clean ordered list of candidate target values.

Two-pointer scan per target. Fix the largest element of a triple as the target $t = a[k]$. With $a$ sorted, search for two values that sum to $t$ using the two-pointer technique:

for each k:                 # choose the target a[k]
    lo = 0, hi = n-1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == a[k]: report (lo, hi, k); done
        elif s < a[k]: lo += 1
        else:          hi -= 1

Each two-pointer pass costs $O(n)$, and we run it for each of the $n$ choices of $k$: $\underbrace{O(n)}_{\text{square}} + \underbrace{O(n\log n)}_{\text{sort}} + \underbrace{n\cdot O(n)}_{\text{scans}} = \Theta(n^2).$

Why not faster? This is a Pythagorean-triple search, a special case of the 3SUM problem ($a[i]+a[j]-a[k]=0$). 3SUM is widely believed to require $\Omega(n^2)$ (no sub-quadratic algorithm is known), so among the offered choices the achievable optimum is $\boxed{O(n^{2})}.$

The naive triple loop is $O(n^3)$ (option 2), the $O(n^2\log n)$ of binary-searching each pair (option 3) is beaten by the two-pointer scan, and $O(n\log n)$ (option 4) is below the conjectured 3SUM bound — unattainable.

Exam trick: Any "find $a+b=c$ in an array" task squashes to sort + two pointers, giving $\Theta(n^2)$ — strictly better than per-pair binary search ($n^2\log n$) and the brute-force $n^3$.