Skip equal neighbors after a hit
Updated
After you record a pair, advance L while a[L] equals the used left, and R while a[R] equals the used right. For a fixed i, skip equal i after that i is done.
What to focus on
Skip after a hit, not before. Stop skipping when L >= R. The first copy of a value is the one you used.
Worked examples
skip extra 4
a = [1, 4, 4, 9], target=5- L=0, R=2: 1+4=5 hit
- R -= 1 while a[R]==4 → R=0
- L += 1 → L=1
Result: L=1, R=0 · (1, 4) once
skip extra 1
a = [1, 1, 4, 9], target=10- L=0, R=3: 1+9=10 hit
- L += 1 while a[L]==1 → L=2
Result: L=2, R=2 · (1, 9) once
no extras
a = [1, 4, 9], target=10- L=0, R=2 hit
- L += 1, R -= 1
- neighbors 4≠1 and 4≠9
Result: L=1, R=1
Try it
Write skipAfterHit(a, target). a is a sorted array of integers. target is the pair sum. L is the left index. R is the right index. Duplicates if present are adjacent. After each hit print L and R once duplicates are skipped. Return nothing. On [1, 4, 4, 9] target 5, [1, 1, 4, 9] target 10, and [1, 4, 9] target 10.
a is sorted non-decreasing, length ≥ 2. A hit exists at the current L, R. Duplicates if present are adjacent.
LeetCode problems that use this skill
- 3Summedium