The Two Pointer Technique

Two pointers is how you get hash-map speed without hash-map memory. It only works when the input has an order you can exploit - which is why the first move is so often to sort.

Why it works

A nested loop tries every pair: O(n squared). Two pointers works because each comparison lets you rule out a whole group of pairs at once, so each pointer only ever moves forward. Total movement is n, so the whole thing is O(n).

Variant 1: opposite ends

Start wide, move inward. Needs sorted input.

function twoSumSorted(sorted, target) {
  let left = 0
  let right = sorted.length - 1

  while (left < right) {
    const sum = sorted[left] + sorted[right]

    if (sum === target) return [left, right]

    // Too small? The only way up is a bigger left value.
    if (sum < target) left++
    // Too big? The only way down is a smaller right value.
    else right--
  }

  return []
}

console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10))  // [1, 4]