Two-sum with a value-to-index map08.03
Scan left to right. At j, if target−a[j] is a key with index i≠j, return (i,j). Then put a[j]→j (usually last-index / overwrite). One pass, expected O(n).
Put after the query so you do not pair an index with itself when 2*a[j]==target. Store indices, not just a seen-set, because the answer is indices.
worked examples
Same skill, three traces. Read all three before you try it.
01hit - given
a = [4, 1, 9, 1],t = 10- walk
at
9, need1,1is at index1- result
- (
1,2)
02two 1s - given
a = [4, 1, 9, 1],t = 2- walk
at second
1, need1, first1at index1- result
- (
1,3)
03miss - given
a = [4, 1, 9],t = 8- walk
complements
4,7,−1never hit a prior key- result
- none
Write
Return
twoSum(a, t).a is an array of integers. t is the target sum.Return
0-based indices (i, j), or none. Query the map for t−a[j], then put a[j]→j.a = [4, 1, 9, 1], t = 10 → (1,2).a = [4, 1, 9, 1], t = 2 → (1,3).a = [4, 1, 9], t = 8 → none.constraintsa is a non-empty list of integers. Indices are 0-based. A pair may or may not exist.
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.