Closest-sum with opposite pointers
Updated
Closest-sum tracks the pair whose sum is nearest a target. Same L/R motion as target-sum: too small L += 1, too large R -= 1. Update best whenever |sum - target| improves.
What to focus on
You still visit each pointer at most once. Best starts from the first pair (L=0, R=n-1). A pair always exists.
Worked examples
target 8
a = [1, 4, 9], target=8- L=0, R=2: 1+9=10 dist 2 best
- R=1: 1+4=5 dist 3
- L==R
Result: best (1, 9) sum 10
target 6
a = [1, 4, 9], target=6- L=0, R=2: 1+9=10 dist 4
- R=1: 1+4=5 dist 1 best
- L==R
Result: best (1, 4) sum 5
exact 8
a = [1, 4, 4, 9], target=8- L=0, R=3: 1+9=10 dist 2
- R=2: 1+4=5
- L=1, R=2: 4+4=8 dist 0
Result: best (4, 4) sum 8
Try it
Write closestSum(a, target). a is a sorted array of integers. target is the sum you want to approach. L is the left index. R is the right index. Return the closest pair. On [1, 4, 9] with targets 8 and 6, and on [1, 4, 4, 9] with target 8.
a is sorted non-decreasing, length ≥ 2. A pair always exists.