The Two Sum problem is a common algorithmic problem where we are given an array of integers and a target integer. The goal is to find two numbers in the array that add up to the target.
We can solve this problem efficiently using a hash map (or dictionary) to store the numbers we have seen so far and their indices.

Program Structure

The program consists of a single function, twoSum, which takes an array of integers and a target integer as input.
It returns the indices of the two numbers that add up to the target. The algorithm works in O(n) time complexity, where n is the number of elements in the array.

Go Program

package main

import (
    "fmt"
)

// twoSum function finds two numbers in the array that add up to the target.
// It returns their indices as a slice of integers.
// If no such pair is found, it returns nil.
func twoSum(nums []int, target int) []int {
    // Create a map to store the difference and its index
    numMap := make(map[int]int)
    
    // Iterate through the numbers in the array
    for i, num := range nums {
        // Calculate the required number to find the target sum
        complement := target - num
        
        // Check if the complement is already in the map
        if index, found := numMap[complement]; found {
            return []int{index, i} // Return the indices of the two numbers
        }
        
        // Store the current number and its index in the map
        numMap[num] = i
    }
    
    return nil // Return nil if no pair is found
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    
    if result != nil {
        fmt.Printf("Indices of the two numbers are: %v\n", result)
    } else {
        fmt.Println("No two numbers found that add up to the target.")
    }
}
    

How It Works

1. We create a hash map numMap to store each number and its corresponding index as we iterate through the array.
2. For each number in the array, we calculate the complement needed to reach the target.
3. We check if this complement is already in the map. If it is, we return the indices of the complement and the current number.
4. If the complement is not found, we add the current number and its index to the map.
5. If we finish the loop without finding any valid pairs, we return nil.

Conclusion

This program efficiently solves the Two Sum problem using a hash map to track the numbers and their indices, allowing us to find the solution in linear time.
You can test this program by changing the input array and the target value in the main function.