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

arr=(2 7 11 4 5) and target=9 are the pinned inputs.
declare -A seen=() creates a Bash associative array that maps value -> index.
first=-1 and second=-1 are sentinel outputs until a pair is found.
for ((i = 0; i < ${#arr[@]}; i++)); do scans zero-based indexes 0 through 4.
value=${arr[i]} reads the current value, and need=$((target - value)) uses Bash arithmetic expansion to compute the complement.
if [[ -v seen[$need] ]]; then checks whether the associative-array key exists without reading an unset key under set -u.
On a hit, first=${seen[$need]} and second=$i capture the pair, then break stops after the first match.
On a miss, seen[$value]=$i records the current value and index.

Replay steps

i=0 value 2 need 7: miss, seen {2:0}
i=1 value 7 need 2: hit, result [0, 1]

echo "[$first, $second]" prints exactly [0, 1].

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.