Target-sum with opposite pointers04.06
On a sorted array, L = 0 and R = n-1. If a[L]+a[R] equals target, that is the pair. If the sum is too small, L += 1. If too large, R -= 1.
The array is sorted. Each step moves exactly one pointer, or both after a hit. Stop when L >= R.
worked examples
Same skill, three traces. Read all three before you try it.
01hit 10 - given
a = [1, 4, 9],target=10- walk
L=0,R=21+9=10- result
- (
1,9) at (0,2)
02hit 13 - given
a = [1, 4, 9],target=13- walk
L=0,R=2:1+9=10<13,L=1L=1,R=2:4+9=13- result
- (
4,9) at (1,2)
03miss 8 - given
a = [1, 4, 9],target=8- walk
L=0,R=2:1+9=10>8,R=11+4=5<8,L=1L==Rstop- result
- no pair
Write
Return the hitting pair. Target
On
twoSumSorted(a, target).a is a sorted array of integers. target is the pair sum. L is the left index, start 0. R is the right index, start n-1.Return the hitting pair. Target
10 must yield (1, 9).On
[1, 4, 9] with targets 10, 13, and 5.constraintsa is sorted non-decreasing, length ≥ 2. A target pair exists.
- Two Sum II0/3 skills ready · two pointers · mediumopen
- Two Sum II0/3 skills ready · two pointers · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.