awelgorithms

Two-sum with a value-to-index map

Updated

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).

What to focus on

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

hit

a = [4, 1, 9, 1], t = 10
  1. at 9, need 1, 1 is at index 1

Result: (1,2)

two 1s

a = [4, 1, 9, 1], t = 2
  1. at second 1, need 1, first 1 at index 1

Result: (1,3)

miss

a = [4, 1, 9], t = 8
  1. complements 4,7,−1 never hit a prior key

Result: none

Try it

Write 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.

a is a non-empty list of integers. Indices are 0-based. A pair may or may not exist.

practise it with Awel find your weak spots: free skill check

LeetCode problems that use this skill