Solve Two Sum in O(n) returning the two indices
Implement twoSum(nums, target) returning the indices of the two numbers that add up to target. Requirements: O(n) time — a single pass, not the brute-force O(n²) nested loop. Return the original indices (do not sort and lose them). You may assume exactly one valid pair.
func twoSum(nums []int, target int) []int {
// your code here
return nil
}Write the implementation.
Keep a map[int]int from value → index. Iterate with for i, n := range nums; for each n, look up target-n via comma-ok — if found at index j, return []int{j, i}; else store seen[n] = i. This is O(n), versus the brute-force O(n²) nested scan.
- ✗Sorting first and losing the original indices the problem asks for
- ✗Doing two passes when one pass with comma-ok suffices
- ✗Believing the brute-force nested loop is O(n) on average
- →Why does storing value→index let you find the complement in one pass?
- →How do you handle duplicate values that form the pair, like
[3,3]target 6?
Task
Return the indices of the two numbers that add up to target.
func twoSum(nums []int, target int) []int {
seen := make(map[int]int) // value -> index
for i, n := range nums {
if j, ok := seen[target-n]; ok {
return []int{j, i}
}
seen[n] = i
}
return nil
}How it works
The idea is to remember already-seen numbers in a map[int]int (value → index) in one pass.
For each n, the needed "complement" is target - n. If it was seen before (j, ok := seen[target-n] with the comma-ok pattern), the pair is found: return []int{j, i}. Otherwise record seen[n] = i and continue.
Each element is processed once with an O(1) map lookup, so the total complexity is O(n), versus O(n²) for the naive double loop.
⚠️ Demonstrates idiomatic comma-ok and a hash table instead of brute force.
