The Two Sum problem is a common algorithmic problem where you are given an array of integers and a target sum. The objective is to determine if there are two numbers in the array that add up to the specified target sum.

This implementation uses a hash map (or hash table) for efficient lookup of the required numbers. The time complexity of this solution is O(n), making it efficient for large input sizes.

Program Structure

• Includes and Definitions: Necessary header files and type definitions.
• Hash Map Implementation: A structure to handle the hash map operations.
• Main Function: The logic for the Two Sum problem and handling input/output.

Code Explanation

#include 
#include 

// Define a hash map entry
typedef struct HashMapEntry {
    int key; // The number from the array
    int value; // The index of that number
} HashMapEntry;

// Define a hash map structure
typedef struct HashMap {
    HashMapEntry *entries;
    int size;
} HashMap;

// Hash function to calculate the index
int hash(int key, int size) {
    return abs(key) % size; // Ensure a non-negative index
}

// Function to create a hash map
HashMap *createHashMap(int size) {
    HashMap *map = malloc(sizeof(HashMap));
    map->entries = malloc(sizeof(HashMapEntry) * size);
    map->size = size;
    for (int i = 0; i < size; i++) { map->entries[i].key = 0; // Initialize keys
        map->entries[i].value = -1; // Initialize values
    }
    return map;
}

// Function to insert into the hash map
void insert(HashMap *map, int key, int value) {
    int index = hash(key, map->size);
    while (map->entries[index].value != -1) {
        index = (index + 1) % map->size; // Linear probing
    }
    map->entries[index].key = key;
    map->entries[index].value = value;
}

// Function to find a value in the hash map
int find(HashMap *map, int key) {
    int index = hash(key, map->size);
    while (map->entries[index].value != -1) {
        if (map->entries[index].key == key) {
            return map->entries[index].value; // Return index if found
        }
        index = (index + 1) % map->size; // Linear probing
    }
    return -1; // Not found
}

// Function to solve the Two Sum problem
void twoSum(int *nums, int numsSize, int target) {
    HashMap *map = createHashMap(numsSize);
    
    for (int i = 0; i < numsSize; i++) { int complement = target - nums[i]; int foundIndex = find(map, complement); if (foundIndex != -1) { printf("Indices: %d, %d\n", foundIndex, i); free(map->entries);
            free(map);
            return;
        }
        insert(map, nums[i], i);
    }
    printf("No two sum solution found.\n");
    free(map->entries);
    free(map);
}

// Main function
int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    
    twoSum(nums, numsSize, target);
    return 0;
}

How to Compile and Run

1. Save the code in a file named two_sum.c.
2. Open a terminal and navigate to the directory containing the file.
3. Compile the program using gcc two_sum.c -o two_sum.
4. Run the executable using ./two_sum.

Explanation:

1. C Program: The program uses a hash map to store numbers and their indices while iterating through the array to check for the complement (the number that, when added to the current number, equals the target).
2. Functions:
   • hash(): Computes an index for a given key.
   • createHashMap(): Initializes a hash map.
   • insert(): Adds a key-value pair to the hash map.
   • find(): Looks up a key in the hash map.
   • twoSum(): Main logic to find the two numbers that add up to the target.
3. Main Function: Demonstrates the use of the twoSum() function with a sample array and target.