Two-Sum with Hash Lookup

Walk the array once, storing seen values in a lookup table. When the complement is already present, the result indices are known.

Algorithm

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
arr=(2 7 11 4 5)
target=9
declare -A seen=()
first=-1
second=-1
for ((i = 0; i < ${#arr[@]}; i++)); do
	value=${arr[i]}
	need=$((target - value))
	if [[ -v seen[$need] ]]; then
		first=${seen[$need]}
		second=$i
		break
	fi
	seen[$value]=$i
done
echo "[$first, $second]"

Complexity

Time: O(n) average
Space: O(n)

Implementation notes

Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
The final output is intentionally small and deterministic for cross-language comparison.

execution replay The checked-in replay follows the language-neutral state table for `array-two-sum-hash`.

cross-language comparison This Bash DSA version keeps the same data and final output as every other DSA book in this wave.