Two Sum - C Solution

1. Introduction

In this post, we explore a fundamental problem in array processing and hash tables, known as the "Two Sum" problem. The challenge is to find two numbers in an array that add up to a specific target value. This problem is often encountered in algorithmic interviews and is a great example of applying hash tables for efficient lookups.

Problem

Given an array of integers nums and an integer target, the task is to find indices of the two numbers such that they add up to target. It is assumed that each input has exactly one solution, and the same element cannot be used twice.

2. Solution Steps

1. Create a hash table to store the indices of the array elements.

2. Iterate through the array nums.

3. For each element, check if target - element exists in the hash table.

4. If it exists, return the current index and the index of target - element.

5. Otherwise, add the current element and its index to the hash table.

6. Continue until a solution is found.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Function to return the indices of the two numbers adding up to the target
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* result = (int*) malloc(2 * sizeof(int));
    int hashTable[20001] = {0}; // Assuming the range of numbers is -10000 to 10000
    int complement;

    for (int i = 0; i < numsSize; i++) {
        complement = target - nums[i] + 10000; // Adjust for negative numbers
        if (hashTable[complement] != 0) {
            result[0] = hashTable[complement] - 1;
            result[1] = i;
            return result;
        }
        hashTable[nums[i] + 10000] = i + 1; // Store index + 1 to differentiate from default value 0
    }

    return result; // Solution always exists
}

// Main function to test the twoSum function
int main() {
    int nums1[] = {2, 7, 11, 15}, target1 = 9, returnSize1;
    int* indices1 = twoSum(nums1, 4, target1, &returnSize1);
    printf("Indices: [%d, %d]\n", indices1[0], indices1[1]);
    free(indices1);

    return 0;
}

Output:

Indices: [0, 1]

Explanation:

1. Initialize a hash table to store indices of elements.

2. Iterate through the array and for each element, calculate the complement (target - element).

3. Check if the complement exists in the hash table.

4. If found, return the indices of the current element and its complement.

5. Otherwise, add the current element and its index to the hash table.

6. The main function tests the twoSum function with an example and prints the indices.