Fix one index then face the rest05.05
Three-sum fixes i, then runs opposite pointers on the suffix: L = i+1, R = n-1. The pair at L, R plus a[i] is the triple. Then i += 1 and repeat.
After fixing i, L starts at i+1 not 0. R starts at n-1. L and R never include i. The suffix a[i+1..] is sorted.
worked examples
Same skill, three traces. Read all three before you try it.
01i = 0 - given
a = [1, 4, 9],target=14- walk
fix
i=0(1)L=1,R=21+4+9=14- result
- triple (
1,4,9) ·L=1,R=2
02i = 0 dups - given
a = [1, 4, 4, 9],target=9- walk
fix
i=0(1)L=1,R=3:1+4+9=14>9,R=21+4+4=9- result
- triple (
1,4,4) ·L=1,R=2
03i = 1 no pair - given
a = [1, 4, 9],target=14- walk
fix
i=1(4)L=2,R=2suffix has one cell
- result
- no pair on the suffix
Write
Return the hitting triple.
On
threeSum(a, target).a is a sorted array of integers. target is the triple sum. i is the fixed index. L is i+1. R is n-1.Return the hitting triple.
On
[1, 4, 9] target 14 and on [1, 4, 4, 9] targets 9 and 17.constraintsa is sorted non-decreasing, length ≥ 3. A target triple exists.
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.