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

program array_two_sum_hash
    implicit none
    integer :: arr(5) = [2, 7, 11, 4, 5]
    integer :: seen_value(5), seen_index(5)
    integer :: target, seen_count, first, second, i, j, need
    logical :: found
    target = 9
    seen_count = 0
    first = -1
    second = -1
    found = .false.
    do i = 1, 5
        need = target - arr(i)
        do j = 1, seen_count
            if (seen_value(j) == need) then
                first = seen_index(j)
                second = i - 1
                found = .true.
                exit
            end if
        end do
        if (found) exit
        seen_count = seen_count + 1
        seen_value(seen_count) = arr(i)
        seen_index(seen_count) = i - 1
    end do
    print '("[", I0, ", ", I0, "]")', first, second
end program array_two_sum_hash

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 Fortran DSA version keeps the same data and final output as every other DSA book in this wave.