Two Sum

Find the two indices whose values add to a target.

twoSum([]int{2, 7, 11, 15}, 9)   // [0 1]  — because 2 + 7 == 9

The obvious way

Try every pair:

for i := 0; i < len(nums); i++ {
    for j := i + 1; j < len(nums); j++ {
        if nums[i]+nums[j] == target {
            return []int{i, j}
        }
    }
}

$O(n^2)$. The problem’s own follow-up asks for better, which is a strong hint that the nested loop is the thing to get past.

The inversion

The inner loop is searching for a specific number: target - nums[i]. You already know exactly what you are looking for — you just cannot find it quickly.

So flip what goes in the map. Do not store “here are the values I have”. Store “here is where I saw each value”, and then ask the map for the one you need.

func twoSum(nums []int, target int) []int {
    var seen = make(map[int]int)

    for i, v := range nums {
        if index, ok := seen[target-v]; ok {
            return []int{i, index}
        } else {
            seen[v] = i
        }
    }

    return nil
}

One pass, $O(n)$ time, $O(n)$ space.

Two small things

The else is unnecessary. The if branch returns, so the body below it is already unreachable when a match is found:

if index, ok := seen[target-v]; ok {
    return []int{i, index}
}
seen[v] = i

Go vets flag this shape (indent-error-flow) for the same reason early returns are preferred generally — one less level of nesting, and the happy path stays at the left margin.

The returned order is [i, index] — current index first, earlier index second. This problem accepts any order, so it passes. Worth noticing rather than worth changing, because plenty of problems do care.

Why not sort

Sorting plus two pointers also solves it in $O(n \log n)$ and $O(1)$ space. It is the better answer when memory is tight — and it is the wrong answer here, because sorting destroys the indices, which are what the problem asks for. Recovering them costs the space you just saved.

That distinction is the actual lesson: the output shape decides the technique. Return the values and sorting is fine; return the indices and you want the map.

The family

Once the inversion is visible it recurs everywhere:

• Subarray sum equals K — store prefix sums, look up prefix - k.
• Contiguous array — store the first index of each running balance.
• Longest harmonious subsequence — count values, look up v + 1.

In each one the loop asks the map for a value it computed from the current element, rather than searching for it. The map holds the past; the question is always about what the present needs from it.